Binary Searching
Linear searching is inherently slow compared to other methods of achieving a similar result. Often the value may not be found and processor time is wasted going sequentially through a list/array, etc... Binary searching goes through these steps (assuming the list is not sorted):
1. Sort the list (otherwise we cannot use a divide and conquer method)
2. Begin looking for the value desired in the "middle" of the data structure
3. There are several ways to implement this search method including recursion, multiple iteration, and single iteration.
4. I will use recursion since it is relatively straight forward. We recursively call the function as it searches the list until it either finds the value or reaches the end of the list.
We'll use a crude bubble sort for this example since the list will only have 10 elements.
CODE
srand(time(0));
int arrayOne[10];
int value = 0, found = 0;
//random values for example
for (int i = 0; i < 10; i++)
{
arrayOne[i] = rand() % 10 + 1; //under 10
}
We declare an array with 10 elements and gives it random numbers between 0 and 10 (the allows for easier debugging, if the need arises--always a good plan when developing software...)
Let's ask the user for the value to search for and then sort the list and display it using a crude bubble sort:
CODE
cout << "Enter a value to search for inside the array: ";
cin >> value;
//Sort and then search
BubbleSort(arrayOne, 10);
Here is the actual bubble sort
CODE
void BubbleSort(int number[], int max)
{
for (int n = 0; n < max; n++)
{
int temp = 0;
for (int i = 1; i < max; i ++)
{
temp = number[i];
if (number[i] < number[i-1])
{
number[i] = number[i-1];
number[i-1] = temp;
}
}
}
}//end bubble sort
For display purposes as visual learning is key, we will display the contents of the list before doing the search. This nallows us to modify any possible errors that may arise in our logic for either the sort or the search.
CODE
//Display sorted list
for (int i = 0; i < 10; i ++)\
{
cout << " " << arrayOne[i] << " ";
}
We will now "search" the list for the inputted value:
CODE
found = BinarySearch(arrayOne, value, 0, 9); //crude but this can be altered for dynamic"ness"
if(found == -1)
cout << "\n" << value << " was not found within this list of data\n";
else
cout << "\n" << value << " was found within this list of data\n";
There are several ways to handle the data from the Binary search, the easiest of which is using 1, 0 and -1 to represent true, false, etc... Feel free to experiment as this is by no means the only way to handle the search results. Here is the code for the Binary Search function:
CODE
int BinarySearch(int A[], int value, int low, int high)
{
if (high < low)
{
return -1; // not found
}
int mid = (low + high) / 2;
if (A[mid] > value)
{
return BinarySearch(A, value, low, mid-1);
}
else if (A[mid] < value)
{
return BinarySearch(A, value, mid+1, high);
}
else
{
return 1; // found
}
}//end Binary Search
The key to this search algorithm is the sorted relationship among elements. This can be taken further to be used with classes and other complicated data other then simple integers.
Efficiency: Best case: Assuming the value is found immediately in the "middle" it would O(1) since only one interation or recursive call was needed.
Average case: There are two cases: for searches that will fail because the value is not in the list, the search interval must be successively halved until no more elements remain and this process will require at most the number of probes just defined, or one less. The latter occurs because the search interval is not in fact exactly halved, and the interval could be closed early based on the parameters set (i.e. the user can define multiple searches to be done with varying goals).
Worst case: It must traverse the entire list with no result so we are loking at N-1 iterations since the list is halved. Still not too bad considering other search methods.
edit: It is widely known/accepted that Binary searching operates at O(log n) speeds regardless of case(s) above.Various Binary Search Methods:
Recursive Function
HEREIterative Function
HEREDivide and conquer seems to be the theme of my last few tutorials and it has such wide applications in computer science and programming. Tasks that can be broken down and repetitively done are computers' forte. Happy coding!
This post has been edited by KYA: 18 Jul, 2008 - 10:29 AM
Binary Searching: A Faster Way To Find Your Data, Divide and Conquer
18 Jul, 2008 - 09:11 AM
|