Binary search

This image explains what Binary Search does to search for the element faster. 

Hello everyone, today I am here with a new blog. This will be about Searching Problem and it’s solution: Binary Search Algorithm. This is very crucial algorithm for getting better understanding of searching in Programming as well as for examinations and interviews.

Without further ado, let’s begin with searching problem shall we.

Assume, you have a list of sorted array: [1,2,3,4,5,6,7] and you want to find a specific element from that array, let’s say 5. Then, how would you go about solving this problem? Well, you could go in a for loop looking at each element (Linear Search). However, in this Algorithm the loop might have to run for as much time as the size of the instance of problem. What it means is, it will take 7th loop to discover 7, and if the size of that array is 1000, it would take 1000 steps to search the final element in that sorted array. This is linear search and it is helpful but not the optimal solution.

Let’s look at another algorithm that will give us solution in better time complexity than O(n) of the Linear Search. It is called Binary Search Tree and it works something like this:

Assume you have the same list of sorted array: [1,2,3,4,5,6,7] and you want to find a specific element from that array, let’s say 5, same as before. Then what we can do is:

1. We can start by comparing if the middle element is the element we are searching for. In our case 5.
   • Since middle element is not the element we are searching for we compare middle element with the element we are searching for:
     • If middle element is less than the target element:
       • We discard half of the array by discarding any values that are lower than the middle element including middle element itself.
       • In our case, since 4 < 5 we discard elements 1,2,3 and 4 making our new array [5,6,7]
     • If middle element is greater than the target element:
       • We discard half of the array by discarding any values that are higher than the middle element including middle element itself.
       • In our case, the new array from above [5,6,7] since middle element 6 > 5 we discard values greater than 5 that is 6 and 7, leaving us with final value 5.
     • If middle element is the element we are searching for:
       • Our search has ended.
         • The final left element in array [5] is the element we are searching for.

As you can see when we use Binary Search we can make search a lot faster by using Binary Search instead of Linear search. In fact the worst case of Binary Search is O(logn) which is significant optimization upon O(n) of Linear Search.

Doing that in each search we do this and discard the half of the results from the array, in each loop, until the middle element is the element we are searching for or the final element is the element we are searching for or there is no element in the list array that we are searching for. This is how Binary Search works. Let’s visualize it:

a. Input:

a.i. Array: [1,2,3,4,5,6,7]

a.ii. Key (element we are searching for): 5

b. First we search for 5 in the middle of the array:

Element in the middle of the array: 4

Key: 5

they are not same

c. Since Key is greater than the element in the middle discard lower half of the array i.e. discard elements lower than the key including key, since it is not the element we are searching for. Thus our new array is:

ArrayNew: [5,6,7]

Key: 5

d. Again repeat like you did in step b:

Element in the middle of the Array: 6

Key: 5

They are not same

e. Since key is smaller than the element in the middle of the array we discard higher half of the array including key. Thus our array becomes:

ArrayNew: [5]

Key: 5

They are the same, we have reached our result.

Now since we have a basic idea let’s create an algorithm for it:

1. Start
2. Input:
   • array: [1,2,3,4,5,6,7]
   • key: 5
3. Assign:
   • low = 0
   • high = array.length -1 = 6
4. while(l<=h)
   • Assign: m = MATH.FLOOR((l+h)/2)
   • if(array[m] === key):
     • return m
   • else if(array[m] < key):
     • low = m + 1;
   • else:
     • high = m – 1;
5. return “Such element could not be found in given list”

In the algorithm we are keeping low and high as a mechanism to discard half of the array that does not contain the searched element.

Finally, let’s code this in typescript shall we:

export default function BinarySearch(sortedArray: number[], key: number) {
    let l = 0;
    let h = sortedArray.length - 1;

    while(l <= h) {
        let m = Math.floor((l + h)/2);
        if(sortedArray[m] === key){
            return m;
        } else if(sortedArray[m] > key) {
            h = m - 1;
        } else {
            l = m + 1;
        }
    }
}

Comparison between linear search and binary search is:

Worst Case Linear Search[Searching through each element]: O(n)

Worst Case Binary Search: O(logn)

REMEMBER: Constraint of Binary Search is that the Array must be in sorted order.

So this is it for now. Next time I will be coming up with similar interesting concepts from Computer Science and Programming field. Till then, keep learning, keep coding.

Namastey.