In this post we will discuss on a basic searching technique called as binary search . It searches an element (generally called a key ) from a sorted array.

The array is divided into 2 sub arrays one from middle to start and other sub array from middle to end. If the sorted array is in ascending order and the key element is greater than the middle it searches the right sub array else left sub array and the same process continues in those sub arrays until the key element is found.

PROGRAM :

#include <iostream> using namespace std; int main() { int i, first, last, middle, n, key, array[100]; cout << "How many elements ?\t"; cin >> n; for ( i = 0 ; i < n ; i++ ) { cout << "\nEnter number "<< i+1 << " :\t"; cin >> array[i]; } cout << "\nEnter value to find :\t"; cin >> key; first = 0; last = n - 1; middle = (first+last)/2; while( first <= last ) { if ( array[middle] < key ) first = middle + 1; else if ( array[middle] == key ) { cout << "\n" << key <<" found at position "<< middle+1 << endl; break; } else last = middle - 1; middle = (first + last)/2; } if ( first > last ) cout << "\nNot found!"<< key <<" is not present in the list. "<< endl ; return 0; }

OUTPUT :

Cpp Program to implement Binary Search |

Cpp Program to implement Binary Search |