Binary Search is one the searching algorithm usually used to search element in the array. Binary Search uses the Divide and Conquer technique.

What is Divide and Conquer?

The name itself tells that is to first divide the array and look (conquer) into its different parts.

we use middle element (array[mid]) of the array to divide the array into two parts (We actually do not divide the array, we assume that the array having the different partition on the left and right side of the middle element).

But the important factor is that Binay search can only be implemented on the sorted array. So, without going further, first, we need to sort the array, if it is unsorted.

Binary Search Algorithm

So, with array sorted in ascending order. We find the middle element of the array and match it with the search element. If by luck it matches, then we simply output message “Element has been Found”, else we check whether search element is greater or smaller compared to the middle element of the array.

  • If Smaller – then the search element can be present in the left half of the array because the array is sorted and all the values smaller than the middle element of the array is on the left partition. So we carry on the search process in the left partition of the array.
  • If Greater – then the search element can be present in the right half of the array because the array is sorted in ascending order and all the values greater than the middle element of the array is present on the right partition of the array. So we carry the search process on the right side of the array.

We repeat the same process on the partitioned part of the array. Hence we divide more and more until we find the search element in the array or unless the array index ends.

Binary Search Algorithm

Binary Search Program

Steps for Binary Search

  1. Initialize the array with values.
  2. Sort the array in ascending order.
  3. Compare the search element with the middle element of the array. If searchElement > array[mid] then step 4, else if searchElement is < array[mid] then step 5, else if searchElement == array[mid] then step 6.
  4. Check for the searchElement on the right side of middle element i.e Repeat step 3 on right partition.
  5. Check for the searchElement on the left side of middle element i.e Repeat step 3 on left partition.
  6. Output “Found” and End.
  7. If array index goes out of bounds i.e start > end then it means the search element is not present in the array. Output “Not Found” and End.

C/Java Program for Binary Search

C

Java

Output

Binary Search Program with Output

Binary Search Code

That’s all we need to do in order to implement binary search to search a number in the array. If you have any doubts then do comment below.

Leave a Reply

Close Menu