Binary Search Algorithm

What is Binary search?

Binary search is an algorithm that solves search problems, and its input is a sorted list of elements. If an element you’re looking for is in that list, it returns the position where it’s located. Otherwise, binary search returns -1 or null

Suppose you’re searching for a word that starts with letter M in a dictionary. You could start at the beginning and keep flipping pages until you get to the Ms. But you’re more likely to start at a page in the middle, because you know the Ms are going to be near the middle of the dictionary. In general, for any list of n, binary search will take O(log n) steps to run in the worst case, whereas simple search will take n steps.

Psuedocode w/ illustrations

Name of method:
binarySearch(a, x)

Inputs:
a: The sorted array to search in
x: The value we are searching for in a

As an example we'll use int[]{11, 88, 99, 111, 223, 999, 1028}

Outputs:
the index position where a[i] == x or -1 if not found

Procedures:

1. Define start and range variables
   

2. Set start to 0, and set range to the length/size of a
   

3. While start <= range, do the following:

a. Define a mid variable and set it to (start + range)/2 this will get the middle element

b. If x > a[mid], then set the start variable to mid + 1

else if x < a[mid] set the range variable to mid - 1

c. if a[mid] = x, then return mid

4.Return -1 if the value isn't found

Sample code:

Let's find the index position of:

public class MyClass {
  public static void main(String[] args) {
        System.out.print(binarySearch( new int[]{11, 88, 99, 111, 223, 999, 1028}, 999 ));
  }  

  public static int binarySearch(int[] a, int x){
    int start = 0;
    int range = a.length-1;

    while(start <= range){
        int mid = (start + range) / 2;

        if(x > a[mid]) start = mid + 1; 
        else if(x < a[mid]) range = mid - 1;
        else return mid;
    }
    return -1;
  }
}