Binary Search

We want to come up with an efficient way to find the location of an item in an ordered set. For example, suppose we have an arbitrarily list of numbers in increasing order {a,b,c,d,e,f,g,h,i}. How can we find the position of c?

​

Example: 

Write a program to find the position of 19 in the integer array {1,2,3,4,5,6,7,8,28,19,209}

​

​

We can simply do an exhaustive search. Suppose our int array has elements n elements. We can use a for loop to traverse the entire array to find when we hit the element.

​

Exercise: Find the position of 19 in the integer array {1,2,3,4,5,6,7,8,28,19,209}

​

Code:

for(int i = 0; i < arr.length; i++){

      if(arr[i] == 19){

         System.out.println("index: " + i);

         break;

      }

}

​

In this example, we traversed through the entire array, checking each element to see if it matches 19. When if does, we print this index and break form the loop.

But what if our array is HUGE? Traversing through the entire array can be slow, even for a computer, when there are millions of entries. That's why Computer Scientists designed the Binary Search Algorithm  to make this process more efficient. So what is this algorithm doing anyways? The basic idea behind binary search is to split the array in half and check if our target is higher or lower than the midpoint. Suppose the target is lower, then we'll check 

​

Code:

int binarySearch(int[] arr, int x)

    {

        int l = 0, r = arr.length - 1;

        while (l <= r) {

            int m = l + (r - l) / 2;

  

            if (arr[m] == x)

                return m;

  

            if (arr[m] < x)

                l = m + 1;

​

            else

                r = m - 1;

        }

        return -1;

    }

​

Explanation:

We have an ordered integer array named arr, and an integer x which is the element we are trying to find in the array. We initialize the lower bound to 0, and the upper bound to the highest index of the array. Now, we find the midpoint and compare it with our target. Depending on if the target is lower or higher, we'll change our bounds and continue the process. If the element isn't there, we return -1.

​

​

​

1. Use a Binary Search Algorithm to find the position of 19 in the array {0,5,10,19,20}

2. Use a Binary Search Algorithm to find the position "hi" when the array {"a", "b", "c", "hi", "x", "y", "z"}(Hint: Alphabetical Order is your friend!)

3. Use Binary Search to check if 15 is in the array {1,2,3,4,5,6,7,8,9,10,11,12,13,14,16,17,18,19,20}