Summary: In this tutorial, we will learn what is the Binary Search algorithm and how to use the Binary Search algorithm to search an element in an array.

Introduction to Binary Search Algorithm

In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array.

https://en.wikipedia.org/wiki/Binary_search_algorithm

Binary Search is a Divide and Conquer algorithm that is used to search an element in a linear data structure (such as an array, a linked list, etc).

It compares the search element with the middle element of the array.

If they are not equal, the algorithm looks for the search element into either half of the array.

After every unmatched comparison, the algorithm eliminates the half in which the search element cannot lie.

For example, consider the following array:

Binary Search Algorithm

The array is sorted in ascending order and the target element is 9.

Binary search will first compare 9 with the middle element of the array i.e. 3.

Because the middle element is 3 which is less than 9 and the array is in ascending order, the binary search algorithm eliminates the first half of the array knowing 9 cannot lie in the first half.

Binary Search Program

Again the algorithm compares 9 with the middle element of the second half i.e. 7. Results in no match. Knowing 9 is greater than 7, it eliminates the first of the partitioned array.

In the next round, the algorithm compares the target element with the only left element i.e. 9, and the match is found.

Steps for Binary Search in Programming

  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<array[mid] then step 5, else if searchElement==array[mid] then step 6.
  4. Eliminate the first half of the array (i.e. start=mid+1)and repeat step 3 for the second half.
  5. Eliminate the second half (i.e. end=mid-1) and repeat step 3 for the first half.
  6. Output “Found” and End.
  7. If the 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.

Here is the implementation of the steps in C and Java.

C

Java

Output

Binary Search Program with Output
Binary Search Code

In this tutorial, we learned what is Binary Search Algorithm and how to implement binary search algorithm in C and Java.

Leave a Reply