Binary Search Explained

I believe in order to understand something you need to be able to explain it to somebody else.

In that light here is me helping you helping me. I will try and do this for other data structures and algorithms.

Binary search is a search method for searching in a ordered list. Order in this sense meaning the list has a hierarchy that might be purely numeric/temporal but it also could be lexicographical like alphabetical ordering.

left = 0
right = length of array - 1

while left <= right
   mid = rounded middle of (left + right) / 2
   if mid = target return mid
   if mid > target right = mid -1
   if mid < target left = mid +1

It seems simple enough right? Another way to think of this is we are taking the list checking the middle if the middle is larger we look at the two sub arrays and do the same depending if the middle is larger or smaller.

Worked Example

Let’s say we are looking for 19

Let’s now add the pointers

Now let’s add the mid in python //2 will round up

Since 11 is less than 19 we now make left 17 since we do mid + 1

Now let’s add mid

Since we have reached the target we can exit.

Time/Space complexity

The time complexity for this problem is O(log(n)) and the space complexity is O(1), The reason the time complexity is Log is because we are taking half the array each time. The space complexity is constant, because we are not requiring any additional data to be stored beyond the pointers to left right middle.

FAQ’s

Does the array need to be ordered to work? Yes, though the algorthm will “run” it won’t be possible to get the right answer because a random ordering will mean it would not be able to arrive at the answer.

If the array is unordered wound’t it make sense to sort and search or search the list directly in a brute force manner Excellent question If we use a sorting method like merge sort(my favourite due to it’s consistent performance) that would mean O(nlog(n) to sort + O(log(n) in computer science we would resolve this to O(nlog(n) this is greater than O(n) which is the brute force way of searching an array, meaning sorting and searching would be slower

For more resources on getting started with programming check out my post on How I would Learn Programming from Scratch