Category Archives: binary search

How does binary search work

Given an array of numbers, how do you search for a number? 
The simplest method is to start at the first element and keep comparing until the end of the array. If it is found anywhere in the middle, return it. Otherwise we would reach the end of the array which indicates that the element in not found in the array. This is called linear search. Since this algorithm examines all the elements in the worst case, it’s time complexity is O(n).

Binary search on the other hand runs in O(log n) which is better compared to linear search. Binary search requires the input array to be sorted

Binary search starts by dividing the array in two halves. Then we compare the search element with the middle element, if it matches, we return that index. If the middle element is less than the search element, then we can ignore the left half of the array because all the elements which precede middle are far away from the search element. Hence we can confine our search to the right half only. Similarly if the middle element is greater than the search element, no need to search the right half. We can confine our search to the left half only. The same procedure is repeated until we find the element or, the array size becomes 1.

Let us look at an example to understand this algorithm
Let us consider the input array as [1,2,3,4,5,6,7,8,9] and we want to search for 6. Here is how the algorithm works

step 1: [1,2,3,4,(5),6,7,8,9] – middle element is 5 which is less than 6. So skipping the left half
step 2: [6,(7),8,9] – middle element is 7 which is greater than 6. So skipping right half
step 3: [6] – middle element is 6. match found, so return it.

#include <iostream>
using namespace std;
int array[100];
//takes the following parameters 
//s: search element, lower index, higher index
int bin_search(int s, int low, int high)
{
while( low <= high)
{
// the middle element
int middle = (low + high)/2;
//if match is found, return it
if( array[middle] == s)
return middle;

//if middle element is less
else if ( array[middle] < s)
{
//search the right half
low = middle+1;
}
else
{
//search the left half
high = middle-1;
}
}
return -1;
}
int main()
{
int n; // array size
cin>>n;
int i;
for( i = 0 ; i < n ; i++)
{
cin>>array[i];
}
//search element
int s;
cin>>s;

cout<<s<<" found at: "<<bin_search(s,0,n-1);
return 0;
}

Finding the first occurence of a number in a sorted array.

Let us consider an array of numbers sorted in ascending order which can possibly contain duplicates. How do we find the left most/first occurrence of a given number?
The moment we read searching in a sorted array binary search should come to our mind. But Binary search has a limitation that it just finds out if a particular element exists in the array. If array contains duplicate entries, binary search finds out any matching index. But we want to find out the left most occurrence.

For example let us consider an array [1,2,2,3,4] and we have to find the element 2. The binary search finds out 2 at the index 2(assuming the array index starts with 0) and returns. But we actually have to return index 1 because it is the first occurrence.

One brute-force method is to find the occurrence of the element and keep moving left until we reach the first occurrence. But this approach is not effective. Let us consider an example to understand this.

If the input array contains just one element repeated n times. [1,1,1,1,1]. We want to find out the first occurrence of 1. First we find 1 at the index 2, then we have to traverse n/2 places backwards in this worst case. So the time complexity is O(n) which is as good as linear search.

Then how can we modify the binary search to solve this problem with O(log n) time complexity?

Modify the binary search algorithm such that if a matching entry is found, instead of returning, compare the middle element with the previous element. If they do not match, we found the first occurrence. Otherwise search the left half for the first occurrence. This approach guarantees to take O(log n) time to find that first occurrence. Below is the implementation of this approach in C++.

#include<iostream>

using namespace std;
//modified binary search method to find the first occurence
//of an element in the sorted array
int findFirst(int *array, int d, int l, int h)
{
while( l <= h)
{
int m = (l+h)/2;
//if element is found
if( array[m] == d )
{
//have we reached the beginning of the array
//or middle and it's previous elements are equal?
//search the left half
if( m > 0 && array[m] == array[m-1])
{
h= m-1;
}
else
return m; //we found the first occurence return it.
}
//following two conditions are similar to the binary search
else if ( array[m] < d)
{
l = m+1;
}
else
{
h = m-1;
}
}
return -1;
}

int main()
{
int n;
cin>>n;
int *array = new int[n];
int i;
for( i = 0 ; i < n ; i++)
cin>>array[i];
int x;
cin>>x;
cout<<x<<" found at "<<findFirst(array,x,0,n-1);
delete[] array;
return 0;
}

Finding count of a number in a sorted array

In Competitive programming, learning to use the standard library than coding from scratch saves a lot of time. In this post we will use C++ STL(Standard Template Library) binary search algorithm with an example.
Given a sorted array of numbers, How to find the frequency of a given number?

Here is an efficient algorithm to do it. Use binary search to find the left-most(L), and right-most(R) occurrence of the given number. Then R-L+1 gives us the result. 

C++ STL has two functions namely lower_bound, upper_bound which finds out the left-most and right-most occurrences of a given number in a sorted array.
The lower_bound() function returns an iterator to the left-most element, and the upper_bound() function returns an iterator to one element beyond right-most occurrence. So the difference of these two gives the count.

Here is the C++ code.
 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int getCount(vector<int> & numVector, int d)
{
int result = 0;
vector<int>::iterator left, right;
//find the left-most occurence
left = lower_bound( numVector.begin(), numVector.end(), d );
//find right-most occurence only if the number is present
if( left != numVector.end() )
{
right = upper_bound( numVector.begin(), numVector.end(), d );
result = right-left; //right points to one element beyond.
}
return result;
}
int main()
{
int n;
//read array size
cin>>n;
int i,num;
vector<int> nums;
//read the array
for( i = 0 ; i < n ; i++ )
{
cin>>num;
nums.push_back(num);
}
//read the number to be counted
cin>>num;
cout<<getCount(nums,num);
return 0;
}