Find element using binary search in sorted array

Given an sorted array, Finding whether the element is present or not. If present, print the index of that element

Example

input :

arr[] =  {1, 6, 7, 8, 9, 12, 14, 16, 26, 29, 36, 37, 156}

X = 6 //element to be searched

output :

element found at index 1

Algorithm

Time Complexity: O(Logn)

Given an sorted array A with N elements, Searching for an element X with Low and High variables pointing to starting and ending of an array

1. Till Low is less than or equal to high

    a. Set Mid to the Low + (High - Low)/2
    b. If the element at the Mid index is equal to the searched element, return Mid
    c. If the element at the Mid index is less than the searched element, than we need to search on right array, so update Low = Mid + 1
    d. If the element at the Mid index is greater than the searched element, than we need to search on left array, so update High = Mid - 1

This is an iterative procedure which keeps track of the search boundaries via two variables (Low and High).

C++ Program

#include <bits/stdc++.h>
using namespace std;

int Binary_search(int arr[] , int X, int low ,int high)
{
	
	while(low <= high) // till low is less than high i.e. there is atleast one integer in the considered part of array
	{
		
		int mid = low + (high - low)/2; //compute the middle index
		
		if(arr[mid] == X) //if equal then return
			return mid;
			
		else if ( arr[mid] < X) //if smaller then increase the lower limit
			low = mid + 1;
			
		else //if larger then decrease the upper limit
		high = mid - 1;
	}

	return -1;
}

int main()
{
	int arr[] =  { 1,6,7,8,9,12,14,16,26,29,36,37,156}; //array
	int N = sizeof(arr)/sizeof(arr[0]); //size of array
	int X;
	cin>>X; //element to be searched
	int index = Binary_search(arr,X,0,N-1); //search for the element
	if(index >= 0)
		cout << "Element found at index "<<index;
	else
		cout<<"Element not found in the array";
	return 0;
}
Try It


Next > < Prev
Scroll to Top