Binary Search

The first lesson in the unplugged algorithms book is a binary search. Which I had already studied before but the book gave me a deeper understanding of the concept.

So what is Binary search? well, it is an algorithm which helps in finding any element or let’s call it key in a sorted array optimally.

How? By predicting that the key I need is the middle element of the array then see if the middle element that I choose is less than or greater than the key.

We will have also a left pointer that indicates the first element in the array and a right pointer that indicates the last element in the array.

Therefore, initially, we will have:

first: L(left pointer) which is equal 0

second: R(right pointer) which is equal length of array-1

and lastly, we have M(middle pointer considered as a guessed element) which will be equal to L+R/2.

Then we move the left and right pointers based on the following conditions:

• If the middle element is less than the key we will shift the left pointer to be middle + 1 why? because as the array is sorted if the middle element is smaller than the key then the key obviously will never be before the middle element but it can be after so we change the pointer location to be after the middle which is already not the key and anything before it also will not be the key.
• If it’s greater than the key we will shift the right pointer to be middle - 1 why? if you get why the left pointer moves to be the middle plus one then you will get this one in no time but let's explain it also maybe you understand it from the right kind pointer and not from the evil left one😅 So When the key is less than the middle element then it’s not located after it as all the number come after the middle is bigger than the middle which is already bigger than the key I search for so it’s not wisdom decision to check any element in this area again let’s check the area with a small number at the left of the middle element.

May you not understand it with all this written and you want just example and here it’s if you have an array like this [1,2,3,4,5] the middle element will be 3 and your key are 4 when check the middle element you find it’s less than the key (3 < 4) so we don’t have to check 1 and 2 because already the key is bigger than medium which is bigger than all the elements before it so we will shift left pointer to start from 4 and right stay the same.

I think now it’s obvious how it works so we can start to implement the code itself, There are two approaches in which you can do this algorithm first one is iterative as follows :

the second one is recursive as follows:

So how much improvement do we have using this technique in searching well if you use normal searching you will end up checking every element in the array so if you have an array with 1000 elements in the worst case you will do iterations 1000 times to have the element you need but binary search make you do it in a more optimized way to find the key in the worst case you will see it’s log₂(1000) so if we have an array of 1000 elements the worst case to find the key will be after nearly 10 iterations. So as you can see from 1000 to 10 iterations it’s a big difference and no need to prove more than that to say that this approach is the best for such a case.

And here it’s a summary of the first lesson in the Algorithms Unplugged book hope I have made it clear to anyone who has tackled problems with how the binary search algorithms work. The next lesson will be the Insertion sort algorithm so stay tuned😉.