Example a:012345678 10134681012 Search x=6 midI mid 3 mid2 high 1)amid=x, found 2)amid]>x, x is in the left half of the array, search again 3)amid]x, x is in the right half of the array, search again
Example: -1 0 1 3 4 6 8 10 12 a: 0 1 2 3 4 5 6 7 8 low mid1 mid3 mid2 high Search x=6 1) a[mid]=x, found 2) a[mid]>x, x is in the left half of the array,search again 3) a[mid]<x, x is in the right half of the array,search again
Program--binary search Template<class t> int SortedList<T>: BinarySearch(const T&x)const i int high=n-1, low=0, mid while(low<=high i mid=(low+high)/2 if(a x)low-mid+1 else if(amid]>x)high=mid-1 else return mid freturn-1
Program—binary search Template<class T> int SortedList<T>::BinarySearch(const T&x)const { int high=n-1, low=0, mid; while(low<=high) { mid=(low+high)/2; if(a[mid]<x) low=mid+1; else if(a[mid]>x) high=mid-1; else return mid; }return –1; }
Analysis of binary search time complexity Best case: compare one time Worst case: no longer than the height of the binary search tree Average compare times
Analysis of binary search time complexity: • Best case: compare one time • Worst case: no longer than the height of the binary search tree • Average compare times:
2. Sorted Chain class sorted Chain(program 7-1) Search Delete(program 7-2) Insert(program 7-3)
2. SortedChain class SortedChain (program 7-1) Search ,Delete(program 7-2) Insert (program 7-3)
7.3 Hashing 1. deal hashing O() Another representation of a dictionary is to use hashing Address=hash(key), also called name-address function
7.3 Hashing 1.Ideal hashing O(1) • Another representation of a dictionary is to use hashing • Address=hash(key), also called : name-address function