Binary Search (Divide and Conquer Technique)

Binary Search is the simplest and most well-known example of this paradigm. If a set of n elements is given where the numbers are sorted either in ascending or descending order, this algorithm can be used to search for an element in the given set.

The idea behind this algorithm is that to find an element in the given array, first, we find the element in the middle of the array. If the array is in ascending order and the middle element of the array is lesser than the element we want to search. The element can not be on the left-hand side of the middle element. So the search space is reduced by nearly 50%.

In the next step, we try to find the element in one half of the array, and the other half is rejected. In this step we find the middle element of the respective half of the array and the element is compared with the key, we want to search.

This process is followed until we find the element or size of the searching space becomes one.

Source code of Binary Search

#include <stdio.h> int main() { int i, j, n, *arr, mid, first, last, item; printf("Enter number of elements:\n"); scanf("%d", &n); arr = (int *)malloc(n * sizeof(int)); printf("Enter the elements in ascending order\n", n); for (i = 0; i < n; i++) { scanf("%d", &arr[i]); } printf("\nEnter the element to search\n"); scanf("%d", &item); first = 0; last = n - 1; do { mid = (first + last) / 2; if (item < arr[mid]) last = mid - 1; else if (item > arr[mid]) first = mid + 1; } while (item != arr[mid] && first <= last); if (item == arr[mid]) { printf("\n The element %d found in position: %d\n", item, mid + 1); } else { printf("\n %d not found\n", item); } return 0; }

---

Happy Exploring!