Skip to main content

Binary Search & The Kahini!

 Suppose you are given an array of numbers and you need to find whether the number X is in the array. The straight forward approach to do that would be to run a loop and compare each number in the array with X. This is what the pseudo code would look like:

function findNumber(A, x)
  for i = 0 to length of array A
    if A[i] == x
      return true
  return false

For example, let’s assume you are given this array:

[7, 14, 17, 21, 35, 60, 92, 121, 155]

And, you were looking for the number 92. The loop would start checking each of the number in the array against 92 and would find after iterating through the array 7 times.

The worst case time complexity of this approach would be O(n).

However, whenever the array itself is in sorted order (like in this case where the numbers are increasing in value from left to right of the array), you can perform something that is much more efficient: binary search.

The prerequisite of binary search is that the array should be sorted.

How Does Binary Search Work?

Let’s use the same array as an example here:

[7, 14, 17, 21, 35, 60, 92, 121, 155]

The numbers are sorted in increasing order, so it satisfies the prerequisite of binary search. Here, the length of the array (N) is 9. The value of the element in the middle is 35. The starting index is 0, the ending index is 8, and the middle index is 4 [(0+8) / 2].

To look for 92 in this array, we need to first compare the middle value with 92. Since 92 is larger than 35, it can be said that all of the values in the array to the left of 35 will definitely be smaller than 92. And, if 92 were to exist in the array, it would exist to the right of 35 (where the values larger than 35 are).

7, 14, 17, 21, 35, [60, 92, 121, 155]

We will now move our starting index immediately to the right of the middle index:

Start = Mid + 1 = 4 + 1 = 5

Our middle index will now change as well:

Mid = \lfloor{(Start + End) / 2}\rfloor = \lfloor{(5+8) / 2}\rfloor = 6

Now that we have a new middle value, let’s compare it with the number we are looking for. At index 6, we have 92 and turns out that is the number we are looking for. So, we have found 92 in our array.

In this approach we had to perform just two comparisons which is much more efficient than the approach we saw at the beginning of this tutorial.

Another Example

Let’s look at another example: We have the same array, but now we are looking for the number 17.

We begin with the starting index 0, ending index 8 and middle index 4. We compare the middle value (35) with the number we are looking for (17). The number we are looking for is smaller than the middle value. Therefore we can say that the number 17 can exist only on the left half of the array.

[7, 14, 17, 21], 35, 60, 92, 121, 155

To narrow down our search in the next step, we will move the ending index to the left of the middle index:

End = Mid - 1 = 4 - 1 = 3

We will then recalculate our middle index:

Mid = \lfloor{(Start + End) / 2}\rfloor = \lfloor{(0+3) / 2}\rfloor = 1

Now our middle index is 1 and middle value is 14. Comparing the value with 17, we see that the middle value is smaller than the number we are looking for. Therefore, the number we are looking for can only appear on the right of the middle index.

7, 14, [17, 21], 35, 60, 92, 121, 155

So, we shift our starting index to the right of the middle index:

Start = Mid + 1 = 1 + 1 = 2

And, we recalculate our middle index:

Mid = \lfloor{(Start + End) / 2}\rfloor = \lfloor{(2+3) / 2}\rfloor = 2

Now our middle index is 2 and middle value is 17. And, 17 is the number we were looking for.

What If The Number Doesn’t Exist?

Let’s use the same array, but this time we will look for the number 51.

Initially our starting index is 0, ending index is 8, and middle index is 4. The middle value is 35, which is smaller than the 51 (the number we are looking for). Therefore we shift our search to the right half of the array:

7, 14, 17, 21, 35, [60, 92, 121, 155]

We recalculate our starting and middle indices. Following the math outlined above, the new starting and middle indices would be 5 and 6 respectively. The middle value is now 92.

7, 14, 17, 21, 35, [60], 92, 121, 155

Since 51 is smaller than 92, we shift our search to the left. We recalculate our ending and middle indices. The new values of the ending and middle indices are now 5 and 5 respectively. The number 60 is larger than the number we are looking for and so we try to shift to the left one more time.

The new ending index is now 4. Since the ending index has moved to the left of the starting index (i.e. the starting index is greater than the ending index) we can stop our search.

In the situation where the ending index is less than the starting index, it can be concluded that the number we are looking for doesn’t exist in the array.

The Algorithm

Here is what the pseudo code of binary search would look like:

function binarySearch(A, x)
  let start = 0
  let end = length of array A
  while start < end
    let mid = (start + end) / 2 # Integer division
    if A[mid] == X
      return true
    else if X > A[mid]
      start = mid + 1
    else if X < A[mid]
      end = mid - 1
  return false

Since at every step we are reducing the search space by half, the worst case time complexity of binary search is O(log(N)).



Problems List: https://a2oj.com/category?ID=40

Comments

Popular posts from this blog

Game Theory with examples

Game Theory with examples Introduction In this article I will be covering problems related to two players game in which it is assumed that both players play optimally and we have to find out the winner of the game. First we will look at the  basic   division of positions to winning and losing . Then we will see the  Game of Nim  and then see how it will be used to solve the  Composite games . Basic Division of positions to winning and losing Problem Statement:  Consider a simple game played by two players A and B . There are n stones on the table. Each player can pick 1 , 2 or 5 stones in each turn. Both players pick the stones alternately until the total number of stones left on the table is 0. The player unable to make the move will lose. Assuming that both the players play optimally, output the winner of the game. Solution:  As you can see positions 1 , 2 and 5 are winning positions since the player can pick up all the stones and other player will n...

Breaking The Summation Formula (Part 1)

 Q. f ( n ) =  - 1 + 2 - 3 + .. + ( - 1) n n .  Given n, find out f(n) Approach(1)- Bruteforce: 1. Calculation sum=n*(n+1)/2 2. loop[i=1,i=n : i+=2] odd+=i 3.ans=sum-2*odd Code: #include < bits / stdc ++. h > using namespace std ; int main (){   long long x ; cin >> x ; long long p =( x *( x + 1 ))/ 2 ; long long bad = 0 ; for ( long long i = 1 ; i <= x ; i += 2 ) bad += i ; cout << p - 2 * bad << endl ; } Approach(2)-Greedy: Basic: s=1+2+3+4+....+n Formula: sum=n*(n+1)/2= (n/2) + (n+1).2 ...

NT Part 2: Generating Primes, Prime Test, Prime Factorization

  Generating primes fast is very important in some problems. Let's cut to the chase and introduce Eratosthenes's Sieve. The main idea is the following. Suppose we want to find all primes between 2 and 50. Iterate from 2 to 50. We start with 2. Since it is not checked, it is a prime number. Now check all numbers that are multiple of    except  2. Now we move on, to number 3. It's not checked, so it is a prime number. Now check all numbers that are multiple of  ,   except  3. Now move on to 4. We see that this is checked - this is a multiple of 2! So 4 is not a prime. We continue doing this. Here's the implementation. #include <stdio.h> int primechk [ 21000 ] ;   void preprocess ( void ) { int i, j ; for ( i = 2 ; i <= 20000 ; i ++ ) { primechk [ i ] = 1 ; } for ( i = 2 ; i <= 20000 ; i ++ ) { if ( primechk [ i ] == 1 ) { for ( j = 2 ; i * j <= 20000...