Binary Search

A 'divide and conquer' technique to search the list

How it works?

First, the search item is compared with the middle element of the list. If the search item is less than the middle item of the list, we restrict the search to the upper half of the list; otherwise, we search the lower half of the list.

Source Code

#include <iostream.h>

int BinarySearch(int [], int, int);

int main()
{

const int NUMEL = 10;
int nums[NUMEL] = {5,10,22,32,45,67,73,98,99,101};
int item, location;

cout << "Enter the item you are searching for: ";
cin >> item;
location = BinarySearch(nums, NUMEL, item);
if (location > -1)
cout << "The item was found at index location "
<< location << endl;
else
cout << "The item was not found in the list\n";

return 0;
}

// this function returns the location of key in the list
// a -1 is returned if the value is not found

int BinarySearch(int list[], int size, int key)

{
int left, right, midpt;

left = 0;
right = size - 1;

while (left <= right)
{
midpt = (int) ((left + right) / 2);
if (key == list[midpt])
{
return midpt;
}

else if (key > list[midpt])
left = midpt + 1;
else
right = midpt - 1;
}

return -1;
}

Home      Disclaimer      Advertise      Contact us     

Copyright © 2006-08 Paked.com. All rights reserved.

Note: Site best viewed at 1024 x 768 or higher screen resolution