C++ Programming Code Examples C++ > Sorting Searching Code Examples C++ Program to Compare Binary and Sequential Search C++ Program to Compare Binary and Sequential Search - Implement both binary and sequential search. - The time complexity of Binary search is O(log(n)). - The time complexity of Linear search is O(n). - Implement the binary search and count the number of iteration to compute the result. - Implement the linear search and count the number of iteration to compute the result. - Compare the number of iteration and show the better algorithm. - Exit. #include<iostream> using namespace std; // A function implementing Binary search on a sorted array. int BinarySearch(int a[], int start, int end, int item, int iter) { int i, mid; // Every time this function called, counted as a iteration of binary search. cout<<"\niteration "<<iter+1; iter++; // Assigning middle of the array. mid = start + (end-start+1)/2; // If value is less than value at start index more than end index then item is not in the array. if(item > a[end] || item < a[start] || mid == end) { cout<<"\nNot found"; return iter; } // Return if item found at mid index. else if(item == a[mid]) { cout<<"\n item found at "<<mid<<" index."; return iter; } // Return if item found at start index. else if(item == a[start]) { cout<<"\n item found at "<<start<<" index."; return iter; } // Return if item found at end index. else if(item == a[end]) { cout<<"\n item found at "<<end<<" index."; return iter; } // According to the item value choose the partion to proceed further. else if(item > a[mid]) BinarySearch(a, mid, 19, item, iter); else BinarySearch(a, start, mid, item, iter); } // A function implementing Binary search on a sorted array. int LinearSearch(int a[], int n, int item) { int i; for(i = 0; i < n; i++) { cout<<"\niteration "<<i+1; // Directly comparing the item with the array element sequentially. if(a[i] == item) { cout<<"\n item found at "<<i<<" index."; // Returning the number of iteration taken place. return i+1; } } cout<<"\nNot found"; } int main() { int n, i, Biter, Liter, a[20]={1, 9, 16, 24, 28, 35, 39, 43, 49, 53, 55, 66, 67, 73, 75, 77, 83, 89, 96, 97}; cout<<"\nEnter the element to be searched: "; cin>>n; cout<<"\n\n\t\t\tBinary Search :"; cout<<"\n\t\t\t*************"; Biter = BinarySearch(a, 0, 19, n, 0); cout<<"\n\n\t\t\tLinear Search :"; cout<<"\n\t\t\t*************"; Liter = LinearSearch(a, 20, n); // Comparing the number of iteration and printing the better approach for this search. if(Liter > Biter) cout<<"\n\nBinary search is better for this search."; else if(Liter < Biter) cout<<"\n\nLinear search is better for this search."; else cout<<"\n\nBoth are equally efficient for this search."; return 0; }