** Binary Search** finds the position of a specified value

**(key)**in a sorted array.In each step it discards half of the elements to search , thus the worst case

**running time**of binary search is

**O(log n)**.

Binary search follows these simple steps :

1. Compare the middle element of the array with key if middle element is same as key return the index of the middle else go to step 2

2.if middle element greater than key binary search for the key in the left half of the array (start to middle-1) , if its less than key binary search for the key in the right half of the array (middle+1 to end) .

3.repeat this till the size of array to search reduces to zero.

For more information on binary search visit http://en.wikipedia.org/wiki/Binary_search_algorithm

Below is the **C++ code for binary search** algorithm.

**CODE**:

/* http://randomtechbits.in/ *Program to search a number in a sorted array usingBINARY SEARCH*inputs: N- number of integers to sort ,A-array of integers,NUM -the number to search for *output: position of number in the array *code tested on devc++ IDE */ #include<iostream> #include<conio.h> using namespace std; int binarysearch(int A[],int NUM,int low,int high) {int mid; if(low>high)return -1; else mid=low+(high-low)/2; if(A[mid]==NUM) return mid; else if(A[mid]>NUM) return binarysearch(A,NUM,low,mid-1); else return binarysearch(A,NUM,mid+1,high); } main() { int N,NUM,pos; int *A; int i,j; cout<<"Enter the number of elements in te sorted array:\n"; cin>>N; A=new int[N]; cout<<"Enter the array\n"; for(i=0;i<N;i++) cin>>A[i]; cout<<"Enter the number to search for\n"; cin>>NUM; pos=binarysearch(A,NUM,0,N); if(NUM!=-1) cout<<"\nNumber found at postion at "<<pos<<" in the array"<<"\n"; else cout<<"\nNumber not found in the array"<<"\n"; //for more codes visit randomtechbits.in getch(); }