Binary Search

Binary search is used to find the location of a value in a sorted array. It is proven to be the fastest way to find the value.

Algorithm

The program starts from the middle of the array and checks if it is a match with the value. If not, we want to check whether the mid value is greater or less than the search value. If less, then we can ignore/cut off all the values greater than or equal to the mid value and vice versa if greater. We then repeat the process on the section of the array. This goes on until we either find a match or when there is no way to continue dividing the array.

Step by Step

The program undergoes a series of steps:

  1. Finds the middle and checks if it is equal to the value.
    1. If it is a match, the program returns the place of the value.
    2. If not… step 2.
  2. Checks if the value is less than or greater than the middle.
    1. If it is less than the middle:
      1. The high is moved to one less than middle.
      2. A new middle is found between the low and the high.
      3. Return to the original step one.
    2. If it is greater than the middle:
      1. The low is moved to one greater than the middle.
      2. A new middle is found between the low and the high.
      3. Return to the original step one.

Visual Binary Search

Binary_Search.JPG

Code

public static int binarySearch (int[] x, int value) {
        int  low   = 0,
             high  = x.length - 1,
             mid;
        while (low <= high) {
            mid = (low + high) / 2;
            if (x[mid] > value) { 
                   high = mid - 1; 
            }
            else if (x[mid] < value) {
                    low = mid + 1;
               }
            else {
                    return mid;
            }
       }
       return -1;
}

The method returns a -1 if the value is not found in the array because an array cannot have a negative index.

Run-time

Best case

The best case scenario is when the value you are searching for is in the middle of the array, which will have a run-time of O(1).

Worst case

The worst case is when the value being searched is not in the array. the method will run log2n times (see).

Recursive

Code for doing Binary Search recursively.

Code

    public static void main(String[] args) {

        int[] x = {2,4,6,7};
        System.out.print(binary(x, 6));
    }

    public static int binary(int[] x, int ans){
        return binary(x, x.length-1, 0, ans);
    }

    public static int binary(int[] x, int high, int low, int ans){

        int mid = (high + low) / 2;

        if( x[mid] == ans){
            return mid;
        }
        else if(high < low){
            return -1;
        }
        else if(x[mid] > ans){
            return binary(x, mid - 1, low, ans);
        }
        else{
            return binary(x, high, mid + 1, ans);
        }
    }

Note: method overloading is used to create two binary methods.
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License