Tag Archives: binarysearch

Binary Search

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 using BINARY 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();   
}