Binary search in C++

"Sequential search" and "binary search" are one of the most important concepts in C++.I have  discussed the concept of sequential search previously.So, today I am going to discuss the concept of binary search in C++.

Binary search

Binary search is a quicker method of searching for value in an array.It is very quick but remember that it can only search a sorted array.It cannot be applied on an unsorted array.

Procedure

The following steps should be followed to search a number in an array by this method.

• It locates the middle element of array and compares with the search number.
• If they are equal, search is successful and the index of middle element is returned.
• If they are not equal, it reduces the search to half of the array.
• If the search number is less than the middle element,it searches the first half of array.Otherwise it searches the second half of the array.The process continues until the required number is found or loop completes without successful search.

The following program demonstrates the concept of binary search in C++.

Source code

#include<iostream>

#include<conio.h>

using namespace std;

void main( )

{

int array[10]={10,20,30,40,50,60,70,80,90,100};

int n;

int mid;

int start=0

int end=9;

int loc=-1;

int i;

cout<<"Enter any number:";

cin>>n;

while(start<=end)

{

mid=(start+end)/2;

if(array[mid]==n)

{

loc=mid;

break;

}

else if(n<array[mid])

end=mid-1;

else

start=,id+1;

}

if(loc==-1)

cout<<"Number not found."<<endl;

else

cout<<"Number found at index:"<<loc<<endl;

getch( );

}

Output

Enter any number:40

Number found at index:3