Binary Search in an Array

Photo by Daniel Lerman on Unsplash

Suppose that we have a sorted array haystack, with length N and a needle. Let's also suppose that the array is sorted in a non decreasing order.

Binary search works by checking the middle of the array and splitting the array in two parts. If the element in the middle is larger than the needle, we take the first part of the array, else we take the second part. Let's take an example. Consider the following array,

haystack = [10, 15, 17, 21, 29, 32, 78, 100]
needle = 78

In the first pass we check the middle element. How do we find the middle element? We use the position of the first and the last element in the array.

first = 0
last = N - 1
middle = ( first + last ) / 2

The value of N is 8 in our case. So middle would be,

first = 0
last = 8 - 1 = 7
middle = ( 0 + 7 ) / 2 = 3.5

Oh!

3.5 is not a valid index, so let's use only the interger part 3. That makes

middle = 3

Now we can check if the value at the middle index is equal to the needle. If it is, then we have found the number and so we can return the index.

if(haystack[middle] === needle) {
	return middle
}

If needle is not equal to the middle value then we need to check if the middle value is greater than the needle or lesser. If the middle value is greater, that means the needle can only be somewhere in the first half of the array - somewhere between 0 and middle.

if(haystack[middle] > needle) {
    first = 0
    last = middle - 1
}

On the other hand if middle value is less than needle that means the needle can only be in the second part of the array -  somewhere between middle and N.

if(haystack[middle] < needle) {
    first = middle + 1
    last = N - 1
}

Now all we need to do is to repeat this process untill we find the needle or there is no more haystack left. Let's go back to our example.

haystack = [10, 15, 17, 21, 29, 32, 78, 100]
needle = 78
N = 8

first = 0

last = N - 1
     = 8 - 1
     = 7

middle = floor(( first + last ) / 2)
       = floor(( 0 + 7 ) / 2)
       = floor(3.5)
       = 3

The value haystack[3] is 21 which is less than than the needle. So we take the second part of the array.

first = middle + 1 
      = 3 + 1 
      = 4

last = N - 1
     = 8 - 1
     = 7

middle = floor(( first + last ) / 2)
       = floor(( 4 + 7 ) / 2)
       = floor(5.5)
       = 5

The value at haystack[5] is 32 which is still less than the needle. So we can again divide the array is two parts and take the second one.

first = middle + 1 
      = 6

last = N - 1
     = 7
  
middle = floor(( 6 + 7 ) / 2)
       = 6

The value at haystack[6] is equal to the needle and therefore... we are done.

Let's combine all of this and write the pseudocode.

Function BinarySearch(needle, haystack)
    first = 0
    last = LENGTH(haystack) - 1
    
    WHILE first <= last
        middle = floor((first + last) / 2)

        IF haystack[middle] == needle
            RETURN middle
        
        IF haystack[middle] > needle
            last = middle - 1
        
        ELSE
            first = middle + 1
    
    RETURN LENGTH(haystack)
            

We are reducing the size of the array into half with every iteration, that makes the worst case complexity for binary search O(log n).

In other words if we have an array of size 1024, we will be able to find any element in 10 iterations. Sequential or linear search would take 1024 iterations for the same array. As you can see binary search is a hunderd times better the linear search for an array of size 1024. This performance benefit increases with the size of the array.

Elements Linear Search (Iterations) Binary Search (Iterations)
10 10 4
100 100 7
1,000 1,000 10
10,000 10,000 14
100,000 100,000 17
1,000,000 1,000,000 20

Try to solve the problem in Hashjar Arena before moving on to the solution.

Find an element in a sorted array using Binary Search


Now let's look at how to implement Binary Search in code. Scroll down to find your favorite language. We cover Python, Javascript and Typescript.

Python

def binary_search(needle, haystack):
    first = 0
    last = len(haystack) - 1
    while(first <= last):
        middle = (first + last) // 2
        if haystack[middle] == needle:
            return middle
        
        if haystack[middle] > needle:
            last = middle - 1
        
        else:
            first = middle + 1
    
    return len(haystack)
    
print(binary_search(1, [1, 2, 3, 4, 5]))

Javascript

function binarySearch(needle, haystack) {
    let first = 0
    let last = haystack.length - 1;
    let middle;
    while(first <= last) {
        middle = Math.floor((first + last) / 2);
        if(haystack[middle] == needle) {
            return middle;
        }

        if(haystack[middle] > needle) {
            last = middle - 1;
        }
        else {
            first = middle + 1;
        }
    }
        
    
    return haystack.length;
}
    

console.log(0, binarySearch(-1, [1, 2, 3, 4, 5]))

Typescript

function binarySearch<T>(needle: T, haystack: T[]): number {
    let first = 0
    let last = haystack.length - 1;
    let middle: number;
    while(first <= last) {
        middle = Math.floor((first + last) / 2);
        if(haystack[middle] == needle) {
            return middle;
        }

        if(haystack[middle] > needle) {
            last = middle - 1;
        }
        else {
            first = middle + 1;
        }
    }
        
    
    return haystack.length;
}
    

console.log(0, binarySearch(-1, [1, 2, 3, 4, 5]))

Now that you know how Binary Search or Logarithmic Search works, see if you can solve this problem.

What's wrong with this binary search algorithm?


That's it on Binary Search.

Do you remember that Binary Search only works on sorted arrays? In the next post we will learn about the different ways in which we can sort an array.

HashJar

HashJar