C++ Programming Code Examples C++ > Sorting Searching Code Examples Program to Perform Uniform Binary Search Program to Perform Uniform Binary Search - Implement binary search using a lookup table. - It is an improvement in binary search since table lookup is faster than a shift and addition. - The time complexity is O(log(n)). - Implement the binary search on a sorted array. - For the mid index value of any of the sub-array, instead of calculating refer lookup table. - Exit. C++ program to implement Uniform Binary Search. #include<iostream> using namespace std; // A function to create lookup array. void MakeDelta(int *delta, int N) { int power = 1, i = 0; do { int half = power; power *= 2; delta[i] = (N+half)/power; i++; }while (delta[i-1] != 0); } // A function implementing Uniform Binary search. int UniBinarySearch(int *a, int *del, int key) { int i = del[0]-1, d = 0; flag: // If item found at mid index return to main. if (key == a[i]) return i; // If lookup table vlaue is 0 then no more sub-part of array remain to search hence element not found. else if (del[d] == 0) return -1; else { // Shift to left subpart using lookup array 'del'. if (key < a[i]) { i -= del[++d]; goto flag; } // Shift to right subpart using lookup array 'del'. else { i += del[++d]; goto flag; } } } int main(void) { int i, n = 20,d = 0, pow = 1, index; char ch; int a[20] = {1, 8, 4, 9, 13, 18, 19, 22, 24, 36, 77, 48, 43, 96, 88, 79, 83, 92, 94, 99}; // Determine the size of delta array. while(pow <= n) { pow *=2; d++; } int del[d]; // Create lookup array. MakeDelta(del, n); up: cout<<"\nEnter the Element to be searched: "; cin>>n; // Implement Uniform Binary search and get index value. index = UniBinarySearch(a, del, n); if(index == -1) cout<<"\nItem not found"; else cout<<"\nItem "<<n<<" found at "<<index+1<<" position"; // Ask user to enter choice for further searching. cout<<"\n\n\tDo you want to search more...enter choice(y/n)?"; cin>>ch; if(ch == 'y' || ch == 'Y') goto up; return 0; }