Binary search in C / C++ : coding in C / C++ – 4

Question. You are given a sorted (in non-descending order) array, say of ints. Your task is to figure our whether or not a given number, k is part of the array, and if so, print its index.

Solution.

This is the classic binary search algorithm. This divide-and-conquer approach allows us, in each iteration, to reduce by half the portion of the array in which we need to search for the element. Thus, the running time of the binary search algorithm is O(log n) for an array of size n.

The basic idea is as follows: you compare the middle element of the array with k. If it is equal, obviously we are done. Otherwise, if the middle element is greater than k, then since the array is sorted, we know that k, if it is indeed present, would be present only in the 1st half of the array. Similarly one can figure out what to do if the middle element is smaller than k.

—-

// the function takes a sorted array of ints, A, of size n, and a number k as input.
// it returns -1 if the number is not found. Else, it returns an index where it is found.

void binary_search (int A[ ], int n, int k)

{

int low = 0;

int high = n-1;

while (low <= high)

{

int middle = low + (high – low)/2;

if ( A[middle] == k)

return middle;

else if ( k < A[middle])

high = middle – 1;

else

low = middle + 1;

}

return -1;

}

——-

Note that we use: middle = low + (high – low)/2 instead of middle = (low + high)/2. This is because of the possibility that the latter assignment may result in an overflow error.

——–

In case, we wish to find the 1st index at which k is present, we can modify the above code as follows:

——-

void binary_search (int A[ ], int n, int k)

{

int low = 0;

int high = n-1;

while (low <= high)

{

int middle = low + (high – low)/2;

if ( A[middle] == k)
{

int index = middle;

while (index >= 0 && A[index] == k)

index – – ;

return (index + 1) ;

}

else if ( k < A[middle])

high = middle – 1;

else

low = middle + 1;

}

return -1;

}

——

Now, if we want a recursive version of binary search, we can do something like this:

——

// here start and end denote the starting and ending indexes of the subarray we want to //search in.

void rec_bs ( int A[ ], int n, int start, int end, int k)

{

if (start > end)

return -1;

int middle = start + (end – start)/2;

if ( A [ middle ] = = k)

return middle;

else if ( k < A[middle] )

rec_bs ( A, n, start, middle – 1, k);

else

rec_bs ( A, n, middle + 1, end, k);

}

—–

One can call the function at first using start = 0 and end = n-1.

—–

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: