Search an nelement array for a match with a given key; return the array index of the matching element or 1 if no match is found
In the worst case Binary search makes_{ é }log_{2}nù _{}comparisons
Example:
Assume Binary Search takes 1 msec with 100 elements, then it takes 7*1 msecs with 10000 elements, 16 *(1/7) msecs with 65536 elements
BigO Notation
Function f(n) is O(g(n)) if there exists a constant K and some n_{0} such that f(n)<=K*g(n) for any n>n_{0 . }That is as nà ¥ , f(n) is bounded by a constant times g(n).
Usually g(n) selected among
log n (note log_{a}n=k*log_{b}n for any a and b)
n, n^{k} (polynomic)
k^{n} (exponential)
Template < class DataType> Int SeqSearch(DataType list[ ], int n, DataType key) { for (int i=0; i<n; i++) if (list[i]==key) return i; return –1; }
In the worst case n comparisons are performed. Expected (average) number of comparisons is n/2 and expected computation time is proportional to n. That is, if the algorithm takes 1 msec with 100 elements, it takes ~5msec with 50 elements, ~200 msec with 20000 elements, etc.
Example: Binary Search Algorithm (using a sorted array)
Template < class DataType> int BinarySearch(DataType list[ ], int low, int high, DataType key) {int mid;DataType midvalue;while (low<=high){mid=(low+high)/2; // note integer division, middle of arraymidvalue=list[mid];if (key==midvalue) return mid;else if (key<midvalue) high=mid1;else low=mid+1;}return –1}
HW: Write a recursive function for binary search
Example :
int list[5]={5,17,36,37,45}
Binary Search(list, 0,4,44}
1 mid=(0+4)/2=2
midvalue=36
key>midvalue
low=3
2 mid=(3+4)/2=3
midvalue=37
key>midvalue
low=4
3 mid=(4+4)/2=4
midvalue=45
key<midvalue
high=3
4 since high=3<low=4, exit
return –1 (not found)
Binary Search(list, 0,4,5}
1 mid=(0+4)/2=2
midvalue=36
key<midvalue
high=1
2 mid=(0+1)/2=0
midvalue=5
key=midvalue
return 0 (found)In the worst case Binary search makes_{ é }log_{2}nù _{}comparisons
n  8  20  32  100  128  1000  65536 
log_{2}n  3  5  5  7  7  10  16 
Assume Binary Search takes 1 msec with 100 elements, then it takes 7*1 msecs with 10000 elements, 16 *(1/7) msecs with 65536 elements
n

Sequential Search
O(n)

Binary Search
O(log_{ }n)

100

1 msec

1 msec

500

5 msec

1.3 msec

20000

200 msec

2.1 msec

BigO Notation
Function f(n) is O(g(n)) if there exists a constant K and some n_{0} such that f(n)<=K*g(n) for any n>n_{0 . }That is as nà ¥ , f(n) is bounded by a constant times g(n).
Usually g(n) selected among
log n (note log_{a}n=k*log_{b}n for any a and b)
n, n^{k} (polynomic)
k^{n} (exponential)
Example: f(n)=10^{5}2^{n}+10^{23}n+n^{1000} is O(2^{n})
No comments:
Post a Comment