Searching: Binary Search
24th January 2006 - By Paradochs
Information
- Order: O(log2(n))
- Best Case: O(1)
- Average: O(log2(n))
Description (from wikipedia)
A binary search algorithm (or or binary chop) is a computer science technique for finding a particular value in a linear array, by “ruling out” half of the data at each step. A binary search finds the median, makes a comparison to determine whether the desired value comes before or after it, and then searches the remaining half in the same manner. A binary search is an example of a divide and conquer algorithm(more specifically a decrease and conquer algorithm) and a dichotomic search (more at Search algorithm).
C++ Files and Code Listings
This code has a few built in functions to time the sort and count the number of comparisons.
This code was written and compiled successfully in Visual Studio .NET.
BinarySearch.h
/*
Travis Gadberry
Patrick Hesser
Chris Ladewig
BinarySearch.h
21Mar05
*/
#ifndef BINARYSEARCH_H
#define BINARYSEARCH_H
#include <vector>
#include <time.h>
#include <iostream>
#include "QuickSort.h"
using namespace std;
class BinarySearch {
public:
BinarySearch();
BinarySearch(int *, int);
BinarySearch(const vector<int>);
bool search(int);
double getSearchTime();
int getSearchIncrements();
private:
int * A;
int n;
int increments;
double time;
};
#endif
BinarySearch.cpp
/*
Travis Gadberry
Patrick Hesser
Chris Ladewig
BinarySearch.cpp
21Mar05
*/
#include "BinarySearch.h"
using namespace std;
BinarySearch::
BinarySearch() {
n = 1;
A = new int[n];
A[0] = 0;
increments = 0;
time = 0;
}
BinarySearch::
BinarySearch(int * array, int N) {
n = N;
A = new int[n];
for(int i = 0; i < n; i++)
A[i] = array[i];
increments = 0;
time = 0;
}
BinarySearch::
BinarySearch(const vector<int> V) {
n = V.size();
A = new int[n];
for(int i=0; i<n; i++)
A[i] = V.at(i);
increments = 0;
time = 0;
}
bool
BinarySearch::
search(int key) {
time_t t1, t2;
t1 = clock();
QuickSort* quick = new QuickSort(A,n);
quick->sort();
int * B = quick->getArray();
bool found = false;
int low = 0;
int high = n;
int mid;
while((increments++, low <= high) && (increments++, !found)) {
mid = low+(high-low)/2;
if(increments++, key==B[mid])
found = true; /* found it! */
else if(increments++, key<B[mid])
high = mid-1; /* search the lower part */
else
low = mid+1; /* search the upper part */
}
t2 = clock();
time = (t2 - t1)/CLOCKS_PER_SEC;
return found;
}
int
BinarySearch::
getSearchIncrements() {
return increments;
}
double
BinarySearch::
getSearchTime() {
return time;
}
January 24th, 2006 at 9:08 pm
[...] Binary Search [...]