September 2, 2010
Iterative Binary Search Function
Problem
Given an array of positive integers. Write an iterative version of binary search to find an element in the array
Solution
Binary search can be easily implemented using recursion due to the divide and conquer nature of the algorithm however we can also do it using iteration. Please refer to the code below for more information.
Iterative Binary Search Program in C
Here is the code in C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
//Includes #include <iostream> //STD using namespace std; //Receives input array along with left and right indexes //Returns the index of the search key if it is found //otherwise it returns -1 int IterativeBinarySearch(int A[], int key, int l, int r) { //As long as left index is less than right index while (l <= r) { //Middle element int m = (l + r) / 2; //If the search key on the left half if (key < A[m]) { //Update right index r = m - 1; } //If the search key on the right half else if (key > A[m]) { //Update the left index l = m + 1; } //We found the key else { return m; } } //Key was not found return -1; } //Main function void main() { //Input array (already sorted) int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; //Search for 8 cout << IterativeBinarySearch(A, 8, 0, 9) << endl; } |
Please leave a comment if you have questions or corrections. Thanks
About Author
Mohammed Abualrob
Software Engineer @ Cisco
One Comment
in this program the main function should be int not void