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

February 10, 2011 Leave a comment

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.

—–