C++ Program to implement Binary Search [DEVCPP/GCC]

BINARY SEARCH

Binary Search is a fast searching method and it requires the array elements to be sorted. It uses the principle of Divide and Conquer.

Consider that the sorted array is divided into three parts i.e. middle element, Subarray of elements smaller than middle element (Subarray 1) and Subarray of elements larger than the middle element (Subarray 2). The key element can be found either at the middle index or in any one of the subarrays. A recursive approach is applied to the chosen subarray.

EXAMPLE

Consider the heights of employee in ascending order ranging from 120-150 cm. We will try to find height 150 cm by applying Binary Search.

The index will range from 0-6, thus calculating middle index as (0+6)/2=3. The height at position 3 is 135 cm. Since 135 is not the required height, we will choose a subarray. Since 150 is greater than 135, we will choose subarray 2.

Again calculating mid as (4+6)/2=5. The height at position 5 is 145 cm. Since, 145 cm is not the required height, we will again choose a subarray. Since, 150 cm is greater than 145 cm thus again subarray 2 is chosen.

Calculating mid as (6+6)/2=6 and height at index 6 is 150 cm which is the required height. This is how Binary Search works.

TIME COMPLEXITY

BEST CASE: Element found in the first attempt(Middle of the array).
COMPLEXITY: O(1)

AVERAGE CASE: Element found in any other location.
COMPLEXITY: O(log n)

WORST CASE: Element not found or found in the last attempt.
COMPLEXITY: O(log n)

STEPS

1. Input the array elements.

2. Input the key value.

3. Initialize variables with first and last index of array.

4. Calculate middle index.

5. The given key value is first matched with the middle element. If it matches then corresponding index is returned.
If the key value does not match then the search is applied on one of the subarrays.

6. If the key value is greater than the middle element, then the subarray containing greater elements is selected else the subarray containing smaller elements is selected.

7. Repeat steps 4-6 until element is found or subarray converges into single element.

PROGRAM

//Program to implement Binary Search

#include <iostream>

using namespace std;

int main()
{
int a[10],i,key,mid;
bool found=false;

for(i=0;i<10;i++)
{
cout<<"ENTER A["<<i<<"] ELEMENT: ";
cin>>a[i];
}

cout<<"ENTER ELEMENT TO BE SEARCHED :";
cin>>key;

int first=0,last=9;

while(first<=last)
{
mid= (first+last)/2;

if(a[mid]==key)
{
found=true;
break;
}
else if(a[mid]<key)
{
first=mid+1; //Restricting to subarray containing Larger values
}
else
{
last= mid-1; //Restricting to subarray containing Smaller values
}
}

if(found)
{
cout<<"ELEMENT FOUND AT INDEX: "<<mid;
}
else
{
cout<<"ELEMENT NOT FOUND";
}

return 0;
}

OUTPUT