Binary Search Algorithm in C++

Written by Raza on. Posted in C++

Linear search, as described last time is ineffective for method for finding piece of information, the key from a large list. If you have a database of one hundred thousand people living in Los Angeles, you would surely have a headache if you were to look at each and every element of that database to look for your key. In such situations, Binary Search comes into play. Binary search is a very efficient searching algorithm especially for large amount of data. For binary search to perform, data in the list has to be sorted beforehand. 

 

Basic Structure of Binary Search:

Binary search works on the divide and conquer principle. First of all sort the list in descending order. Then choose the middle value of list and divides that list into left and right two halves. Right half would be of elements greater than the middle value and left half would be of elements smaller than the middle value.

Now check whether your key is smaller or greater than the middle value. If it is smaller, surely it would be in the left half of the list if it exists at all. If it is greater or equal to the middle value, then there is chance of finding it in the right half. Whichever half it could be in, we take that half and discard the other half. Then we take that half we have chosen and again choose a middle value from it, divide it into two halves and look for the key.

Repeat this process until the starting and ending index of the small half-lists become equal. Remember to first check the middle value if it is equal to the key. Through this process, we can search for a key just at the maximum 20 iterations in a list of 2000 elements. Great!

 

Example of Binary Search:

Suppose we have this list with us in pre-sorted form.

5, 6, 8, 11, 14, 16, 18, 20, 23, 25

We follow these steps to search for our key. Size of the list is 10. Its middle would become 5. Our key in this case is 23. The starting element of the list is 5 and ending element is 25.

1. Divide the list into two halves with 5th element as the middle value. The middle value is.

5, 6, 8, 11, 14, 16, 18, 20, 23, 25

 .

2. Check if your key is equal to the middle value or not. If not, proceed to the next step. If yes, then game is over!

.

3. Check whether your key is greater or smaller than middle value. Here it is greater, so we consider the right half for our next step and discard the left half completely.

16, 18, 20, 23, 25

 .

4. Now we have a small list of size 5 and the middle element 20 is at 2nd position.

16, 18, 20, 23, 25

 .

5. As middle value is not equal to the key, check if it is greater or smaller. It is greater, so take the right half of this list and carry on with the search.

23, 25

.

6. Now we are left with a list of just two elements. Mid of 2 is 1. So we select 23 as the middle value.

23, 25

 .

7. Check if key is equal to the middle value. It is. So stop searching anymore and send a message to the user that your key has found. Cheer up!

 .

8. Suppose if the key was 26, then it was not the list. In that case, do not go on making halves of your list because you would go nowhere. Check whether the starting index of the new list is less than its ending index or not. If yes, go ahead with searching process. No, then stop there and tell the user that it is not present there in the list.

Source Code for Binary Search:

Here is a basic source code for binary online search.

 

</p>
<p>&nbsp;</p>
<p>bool binary_search (const int arr[], const int size, const int key)<br />
{<br />
.  int start = 0 ;<br />
.  int end = size - 1 ;<br />
.  int mid = (end + start) / 2 ;<br />
.  while (start <= end)<br />
.  {<br />
.   if (key == arr[mid])<br />
.   {<br />
.    return true ;<br />
.   }</p>
<p>.   else if (key < arr&#91;mid&#93;)<br />
.   {<br />
.    end = mid - 1 ;<br />
}<br />
else if (key > arr[mid])<br />
{<br />
start = mid + 1 ;<br />
}<br />
mid = (end + start) / 2 ;<br />
}<br />
return false ;<br />
}</p>
<p>&nbsp;</p>
<p>.<br />
int main ()<br />
{<br />
.  const int SIZE = 10 ;<br />
.  int arr [SIZE] = {11, 12, 13, 14, 15, 16, 17, 18, 19, 20} ;<br />
.  cout << boolalpha << binary_search (arr, SIZE, 11) ;<br />
}</p>
<p>

 

Employ this method of binary search whenever you need to search for something in a list, small or large. It is the best method to search for a key as it is. You can optimize this source code for finding a key multiple times or finding multiple keys at the same time.

Tags: , , ,