5626463547 | San Jose, CA 95126

Binary Search

The value of binary search is that you can search for whether an item exists in a sorted list, array, etc. without having to look at possibly every single item. Suppose you have a sorted array of integers but you do not know what numbers exist in the array. What you do know is that the array is sorted from lowest to highest, there are 1000 elements in the array, and the number you are looking for is 256. A simplistic approach is to start at index 0, check if it is equivalent to 256, if not, then check the next item, and the next item, until you’ve checked all the items and either found or not found the item.  If 256 was the first item, you would be done on the first comparison. But if it was the last, then you would have made 1000 comparisons.

Binary search helps by reducing the number of comparisons under such worst case scenarios. You still might hit the item you are looking for on the first comparison, and you might hit it on your last comparison. But if there are 1000 elements in the array, it won’t take you 1000 comparisons under a worst-case scenario.

The basic idea behind binary search is to look at the midpoint of the sorted array and compare that value to the target value. If the midpoint value is lower than your target, then the target value is somewhere between the index that is one more than the midpoint and the last index. If the midpoint is higher than your target, then the target value is somewhere between the first index (i.e. arr[0]) and the element one index lower than the midpoint.  If you midpoint value is equal to your target value, then you found it and you’re done. Return true. But if you didn’t find it, then you perform the same approach of looking now at a subset of the array, find midpoint, run comparison, make adjustments, etc.

Obviously, this sounds like you can do this with recursion. And you can. But I here provide two iterative approaches since I think they are fairly easy to see what is going on.

Here is an example of how to perform a binary search against an array of integers:

Here is a version that can be used for generics.

2018-06-07T21:33:36+00:00 January 22nd, 2016|Comments Off on Binary Search