Let us consider the problem of searching a word in a dictionary, in general we directly go to some approximate page [say, middle page] start searching from that point. If the name that we are searching is same then we are done with the search. If the page is before the selected page then we apply the same process for the first half otherwise apply the same process to the second half. Binary search also works the same way. The algorithm applying such a strategy is referred to as binary search algorithm.

Iterative version:-

//iterative binary search which returns index of element int binarySearchIterative(int arr[], int size, int data) { int low = 0; int high = size-1; int mid; while(low<=high) { mid = low + (high-low)/2; //To avoid overflow by (low + high) if(arr[mid] == data) return mid; else { if(arr[mid] < data) low = mid + 1; // search in right half else high = mid - 1; // search in left half } } return -1; }

Recursive version:-

//recursive binary search which returns index of element int binarySearchRecursive(int arr[], int low, int high, int data) { if(low<=high) { int mid = low + (high-low)/2; // To avoid overflow if(arr[mid] == data) return mid; else { if(arr[mid] < data) //search in right half. return binarySearchRecursive(arr, mid+1, high, data); else //search in left half. return binarySearchRecursive(arr, low, mid-1, data); } } return -1; }