Custom Search

 

 

 

 
 

 

Binary Search


Binary Search | Bubble Sort | Selection Sort | Finding Maximum Value | Linear Search | Celsius to Fahrenheit | 10 Pseudo-random numbers | Calculating Average | Swapping Values | Lowercase/ Uppercase


Binary Search - A 'divide and conquer' technique to search the list

Advantage:      Faster than a sequential search

Requirement:  The list must be sorted

C++ Program

#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;
}

 

 

                        

 

 

 

Custom Search
 

Home      Disclaimer      Advertise      Contact      Privacy Policy     

Copyright 2004-15 Paked.com. All rights reserved.

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