Binary Search Algorithm

In this article we are going to learn about Binary Search Algorithm. First we will know What is Binary search algorithm, its definition and a simple example of Binary search. Then we will see the Pseudocode for Binary search algorithm and finally we will see a simple Binary search algorithm program in java. Also, at the end I will specify the Worst, Average and Best Time complexity for the Binary search algorithm.


What is Binary Search?

Binary Search is a very popular searching algorithm and used to solve many searching problem as it is very fast and efficient algorithm.

Binary search can only be used on a sorted list. So if we want to apply binary search on an unsorted list then first we need to sort the list.

As compared to linear search, binary search takes less number of comparisons to find an element and is much faster than linear search.


Binary Search Algorithm Definition

According to Wikipedia Binary Search is defined as follows:

"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. Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array."

So in simple words, Binary search searches for a target element in a sorted list, it first searches for the target element at the middle of the list. There can be 3 cases:

  • Target element is equal to the middle element In this case search stops with success
  • Target element is smaller than middle element In this case the search takes place in the elements below the middle element.
  • Target element is larger than middle element In this case the search takes place in the elements above the middle element.

The above process is repeated until the target element is found or no middle element remains as per the criteria.

Binary Search Example

Consider we have an array: A = [3, 4, 6, 7, 8, 9, 10];

Now if we want to search for the number 4, then Binary search starts its search from the the middle element of the array (4th element: 7). Since 4 is not equal to 7 and since (4 < 7), the search continues in the lower part of array (in elements below 7). Now we again find middle element of the sub array which is (2nd element: 4). Since the middle element 4 is equal to our target element 4, the search stops with a success. But in case the target number (eg. 15) is not present in the array then the search would continue to find the middle element by making sub arrays until no element remains and will stop without success.


Binary Search Algorithm

We will first see the Pseudocode for Binary search algorithm and then see a simple program in java.

Binary Search Algorithm Pseudocode

A very simple Pseudocode for Binary search. Here A is the array of elements and target is the element to be searched.

BINARY-SEARCH(A, n, target)
low = 0
high = n - 1

while low <= high
  middle = (low + high) / 2

  if target < A[middle]
    high = middle - 1
  else if target > A[middle]
    low = middle + 1
  else
    return m

end while

return unsuccessful

Binary Search Algorithm in Java

import java.util.*;

class BinarySearch
{
  public static void main(String[] args)
  {
    int A[] = {3, 4, 6, 7, 8, 9, 10};
    int target;

    Scanner sc = new Scanner(System.in);

    System.out.print("Enter number to find: ");
    target = sc.nextInt();

    if (binarySearch(A, A.length ,target) == -1)
    {
      System.out.println("Element not found");
    }
    else
    {
      System.out.println("Element found at: " + binarySearch(A, A.length ,target) + " index");
    }

  }

  public static int binarySearch(int A[], int n, int target)
  {

    int low = 0; // index of first element of array
    int high = n - 1; // index of last element of array
    int middle;

    while(low <= high)
    {
      middle = (low + high) / 2;

      if (target < A[middle])
      {
        high = middle - 1;
      }
      else if(target > A[middle])
      {
        low = middle + 1;
      }
      else
      {
        // index of the target element in array
        return middle;
      }
    }

    return -1;
  }

}

Binary Search Recursive Implementation in Java

import java.util.*;

class BinarySearch
{
  public static void main(String[] args)
  {
    int target;
    int A[] = {3, 4, 6, 7, 8, 9, 10};

    Scanner sc = new Scanner(System.in);

    System.out.print("Enter number to find: ");
    target = sc.nextInt();

    if (binarySearch(A, 0, A.length-1 ,target) == -1)
    {
      System.out.println("Element not found");
    }
    else
    {
      System.out.println("Element found at: " + binarySearch(A, 0, A.length-1 ,target) + " index");
    }

  }

  public static int binarySearch(int A[], int low, int high, int target)
  {
    // return -1 if target element not found in array
    if (low > high)
      return -1;

    int middle = (low + high) / 2;

    if (target < A[middle])
      return binarySearch(A, low, (middle-1), target);

    else if(target > A[middle])
      return binarySearch(A, (middle+1), high, target);

    else
      // index of the target element in array
      return middle;

  }

}

Compile and run program:

$ javac BinarySearch.java

$ java BinarySearch

Output:

$ java BinarySearch
Enter number to find: 4
Element found at: 1 index

$ java BinarySearch
Enter number to find: 10
Element found at: 6 index

$ java BinarySearch
Enter number to find: 21
Element not found

Binary Search Algorithm Complexity

Time compexity for Binary search algorithm

Worst Case Average Case Best Case
O(log n) O(log n) O(1)

We mainly want to know the worst time complexity of the Binary search algorithm which is O(log n).

Binary Search makes log n comparisons where n is the number of elements in the array and log is the logarithm

This is because at every iteration, Binary search rejects half of the searchable array and therefore array gets halfed after every iteration.

Binary search is therefore faster than Linear Search. But the main limitation of Binary search is that it can only work on sorted list.


From this post we learned

  • What is Binary Search Algorithm
  • Pseudocode for Binary Search Algorithm
  • Binary Search Program in Java
  • Binary Search Recursive Implementation in Java
  • Time Complexity of Binary Search Algorithm

Also check out my post on Linear Search Algorithm


Tags: