Comp 110 Binary Search

Binary Search

Algorithm

1.) Start at the middle element of a sorted array

2.) If the value of the middle element is equal to the value we are search for 

  1. Return it! We are done

3.) If the value we are searching for is less than the value of the middle element 

  1. Go back to step #1 and use the smaller half of the array as the sorted array

4.) Else if the value we are searching for is greater than the value of the middle element

  1. Go back to step #1 and use the larger half of the array as the sorted array

5.) Else no match is found in the search

Java Code Example

//1 public class MyBinarySearch {
//2 
//3 public int binarySearch(int[] inputArr, int key) {
//4         
//5     int start = 0;
//6     int end = inputArr.length - 1;
//7     while (start <= end) {
//8         int mid = (start + end) / 2;
//9         if (key == inputArr[mid]) {
//10             return mid;
//11        }
//12        if (key < inputArr[mid]) {
//13            end = mid - 1;
//14        } else {
//15            start = mid + 1;
//16        }
//17    }
//18    return -1;
    }
}

That might look a little confusing, so let's go through this program line by line.

  1. Class Declaration line
  2. Blank Line
  3. binarySearch method declaration. This method is a public method, with a return value of int, and two parameters. One is an int array, which is going to be the array that we are searching for, and the other is a key, which is the value that we are trying to find.
  4. Blank Line
  5. First Index (Zero)
  6. Last Index (Length of the array minus one, since arrays are zero indexed)
  7. Start of the while loop, where we will loop through every element (if necessary)
  8. Declaration of the middle index (Hint: the middle will change every time the loop starts a new iteration!)
  9. If the key is equal to the middle index of the array, then:
  10. Return the middle index. We found it without having to search for it!
  11. End bracket
  12. If the key is less than the element at the middle index, then:
  13. Make the end index the middle index minus one. This will come into play when the loop iterates again, the middle index will become the middle of the old middle and the start index.
  14. Otherwise (else)
  15. Make the start index the middle index plus one. This will come into play when the loop iterates again, the middle index will become the middle of the old middle and the end index.
  16. (End bracket) Note: We make the index the middle index +/- one because we have already looked at the middle index, so we don't need to include it in our new search
  17. Bracket
  18. If the while loop iterates through the array, and the key is never found, then it will return -1. This is so that if you call the method and it returns -1, you can see that the element is not included in the array, as -1 is not a valid index.


Runtime:

Worst case: O(log(n))

Best case: O(1)

Average case: O(log(n))