Binary Search Algorithm

Binary Search algorithm is one of the most easiest and most used algorithm in computer science. We also naturally tend to use this algorithm in our daily life without exactly knowing it.

Let’s suppose we have an array arr[] with following elements,

arr[] = {2, 3, 5, 8, 9, 10}

One of the most important thing to remember is that the Binary Search algorithm can only be implemented on an array which is either sorted in an ascending or descending order.

Let’s suppose “k” is the element that we need to find.

k = 9

First, we need to find the middle of the array. For that purpose, we need to know the extreme left and extreme right position or index (not element) of the array.

In our case, the extreme left is equal to 0 and the extreme right is equal to 5.

Middle of our array = (Extreme left + Extreme right) / 2

= (0+5) / 2

= 5 / 2 => 2.5 (The value will not be rounded off)

So, at position/index 2 of the array, the residing value will be the middle position or value of the array.

Now, there could be four scenarios that we have to observe.

1st Scenario

We will compare the value residing at the middle position of an array with k. If they both are same then true will be returned , meaning the k will be found and the algorithm will end.

2nd Scenario

If the value residing at the middle position of the array is less than k then the whole left part of the array till the middle value (including the middle value) will be discarded. In the remaining part of the array we again have to find the middle value by using the extreme left and extreme right of the remaining array and this process will continue till the middle value and k both are not same.

3rd Scenario

If the value residing at the middle position of the array is greater than k, then the whole right part to the middle position of the array including the middle value will be discarded. Now, from the remaining part of the array we will have to find the extreme left and extreme right position which will help us to know the middle value of the array. This process will also continue until the k and the middle value both are not same.

4th Scenario

If the extreme right position of an array is less than the extreme left position of an array then k does not exist in the array and the algorithm will return false. In other words, after applying the Binary Search algorithm on the whole array still the middle value is not equal to k then k does not exist in the array.

Pseudo Code for Binary Search

if r < l then // Incase the value is not found
    return false
    
mid <- (l + r) // Formel to calculate the middle position of an array

if k = arr[mid] then // In case "k" is equal to the value ressiding at the
    return true     // middle position of an array. (If "k" is found)

else if k < arr[mid] then
    return Binary-Search (arr, l, mid-1, k)
    
else
    return Binary-Search (arr, mid+1, r, k)

Let’s now apply the Binary Search alogorithm on our previously mentioned array.

arr[6] = {2, 3, 5, 8, 9, 10}

Again the value we need to find k is 9.

Since the first index of an array is always 0, the extreme left position will be 0 and since the last index of the array is 5, the extreme left position will be 5.

l = 0 , r = 5

(0 + 5) / 2 => 2.5 => 2 (The value will not be rounded off)

The value residing at index 2 in the array is the middle value.

Value residing at index 2 of the array is 5. Is 5 equal to the k? No. The middle value of the array or 5 is less than k that’s why now we have to consider the 2nd scenario. According to the 2nd scenario all the values to the left of the middle value (including the middle value) will be discarded. Now, we have to consider the remainig array which looks like this,

Again, the procedure will be applied,

l = 0 , r = 2

(0 + 2) / 2 = 1

Value residing at index 1 is 9. Middle value is equal to 9.

Is the middle value equal to k? The answer is yes and the algorithm will return true and terminate.

Best-Case Scenario

Best-case scenario is Binary Search algorithm is that the algorithm only has to run once, meaning the first middle value will be equal to k. This can also be written as 0(1).

Worst-Case Scenario

Worst-case sceanrio in Binary Search algorithm means that the algorithm has to function n times. This is written as 0(n).