Binary Search

Introduction

let’s suppose you want to find the meaning of “Search” in a dictionary, what method will you prefer to read each and every word from start to end and look for the word “Search” or you will go to the middle page of the dictionary and check if the word at the middle page is alphabetically smaller than the word “Search” if this is true then we can ignore the left part of the dictionary and repeat the same process in the right part of the dictionary. Obviously, anyone would choose the second method because reading each and every word of the dictionary will be very time-consuming and in the second method, we are reducing our area of search. this method of searching is called binary search. Binary search is a searching algorithm for finding the position of an element in a sorted array, an array can be sorted in any order ascending or descending.

# variables name we are going to use

# arry = [10,20,30,40,50,60,70,80,90,100] -> sorted array
# start = 0 -> starting position of the array
# end = len(arr)-1 -> ending position of the array
# mid = start + (end - start) // 2 -> mid of the array
# item = 80 -> we are searching index of 80

In binary search we mainly perform these steps:

• We first find the mid position of the array, and then we check if the element at the mid position is equal to the item we are looking for and if that's true then we return the position of the element.
• if the above condition is not satisfied then we check if the element at the midposition is less than the item we are looking for and if that’s true then we look for the item in the upper half of the array.
• if the above condition is not satisfied i.e element at the mid position of the array is greater than the item we are looking for and if that’s true then we look for the item in the lower half of the array.
• We keep repeating this until the element is found else we return -1

Pseudo code / Algorithm

# step 1 variable initialization 

arr = [10,20,30,40,50,60,70,80,90,100] # -> sorted array
start = 0 # -> starting position of the array
end = len(arr)-1 # -> ending position of the array
mid = start + (end - start) // 2 # -> mid position of the array
item = 80 # -> we are searching index of 80

# step 2 Repeat step 3 while start <= end and arr[mid] != item
# step 3
mid = start + (end - start) // 2 
if arr[mid] < item:
    start = mid + 1
else:
    end = mid-1

# step 4 if the element at arr[mid] == item then we return the index of the item else we return -1

Example

we have an arr = [10,20,30,40,50,60,70,80,90,100] and we have to find the position of element 80, first we will initialize some variable

arr = [10,20,30,40,50,60,70,80,90,100] 
start = 0
end = len(arr)-1
mid = start + (end - start) // 2
item = 80 

• here we see that arr[mid] is less than the 80 i.e 50 < 80, so now we can ignore the lower half of the array and search only in the upper half of the array

• now we have to perform some searching on only the upper half of the array so this is our trimmed array.

where start = 5, end = 9 and mid = 7

this time arr[mid] == item, so we will return the position of the item i.e 7, now let’s write the complete code in python.

Python Implementation for Binary Search

def binarySearch(arr, x, i, j):
    while i <= j:
        mid = i + (j - i) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            i = mid + 1
        else:
            j = mid - 1
    return -1


# driver code
arr = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
x = 80
i = 0
j = len(arr) - 1
result = binarySearch(arr, x, i, j)
print("The Element is at position: ", result)

JavaScript Implementation of Binary Search

function binarySearch(arr, x) {
    while (i <= j) {
        let mid = Math.trunc(i + (j - i) / 2);
        if (arr[mid] === x) {
            return mid;
        } else if (arr[mid] < x) {
            i = mid + 1;
        } else {
            j = mid - 1;
        }
    }
    return -1;
}

const arr = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];
const x = 80;
let i = 0;
let j = arr.length - 1;
const result = binarySearch(arr, x, i, j);
console.log("Searching element is present at the location:", result);

Time Complexity

As you might have noticed, each array's comparison size is reduced to half, so its complexity equation is T(n) = T(n/2) + c . So the time complexity of the binary search in the worst case is

Limitations

Binary Search is a very efficient algorithm it requires only about 20 comparisons to search for an element on a list of about a million elements, but it doesn't mean that we don't need any other searching algorithm. For using the binary search algorithm list must be sorted and storing data in an array is very expensive.

Conclusion

That's it for this blog, I have only tried to explain binary search using an iterative approach, but it can later be optimized using recursion. If you think there is something incorrect then please write it down in the comment and I will try to improve that asap.