Introduction
This blog will discuss binary search and various inbuilt library functions to do a binary search in different languages. Before jumping into the discussion of binary search, let's first recall what is searching and what is linear search.
Searching is a technique to find whether the given element exists or not in a given array, and if it exists, then what is its position? Binary search is a technique for searching an element in a sorted array.
Also see, Introduction to Binary Search Tree
Let's assume an array of integers:
arr= [1, 7, 6, 8, 9, 4], and we have to find if “8” exists in the array or not, and if it exists, we have to find its position in the array.
The linear search technique is to traverse the whole array linearly and check if the current element equals the given element. If it is equal to the given element, return its position, and move to the next position. After traversing the array, return that the element doesn't exist if the element is not found.
The time complexity of this algorithm is O(N), where 'N' is the number of elements in the given array.
How do we reduce the time complexity or say how to perform the searching operation in less time.
We can reduce the time complexity of searching in a sorted array by using binary search. Let's assume that we have an array sorted in increasing order, and we have to do a binary search in it for a given element. We divide the array into two parts in binary search and compare the given element with the middle element. If the middle element is equal to the given element, then we return that position. Suppose the middle element is larger than the given element. In that case, it means that the given element will either lie in the left of the middle element or won't exist, so now the problem will reduce to searching the given element in the left half of the array. Similarly, if the middle element is smaller than the given element, the problem will be reduced to search the element in the right half of the array.
(See, Difference Between Binary Tree and BST)
Let's understand the binary search algorithm by taking an example:
The array we have taken above:
arr = [1, 7, 6, 8, 9, 4]
After sorting it in increasing order,
arr = [1, 4, 6, 7, 8, 9]
Now, we have to search for '8' in this array. In this array, the middle element is '6', and '6' is smaller than '8', so we must search in the right half. So the array in which we have to search will be reduced to [7, 8, 9]
Now the middle element is '8', so we have found '8', so return the index of '8'.
If your thinking ability is paused in perplexity, then you must visit the Binary Search article on the Coding Ninjas platform.
Recommended: Binary Search problem for practice on Coding Ninjas Studio.
C++ Code for Binary Search
#include<bits/stdc++.h>
using namespace std;
int binarySearch(int arr[], int k, int n)
{
/*
n = number of elements in the array
k = The element which we have to search in the given array
*/
int start = 0, end = n - 1;
/*
Start and end will be the index of the first and last element of
that part of the array in which we are searching
*/
while(start <= end)
{
// mid is the index of the middle element
int mid = (start + end) / 2;
if(arr[mid] == k) return mid;
/*
middle element is less than k, so now we have to search in the
right half
*/
else if(arr[mid] < k) start = mid + 1;
/*
middle element is greater than k, so now we have to search in
left half
*/
else end = mid - 1;
}
// if element not found return -1
return -1;
}
int main()
{
int arr[6] = {1, 4, 6, 7, 8, 9};
// Search k in the given array
int k = 8;
int foundAt = binarySearch(arr, k, 6);
if(foundAt == -1)
cout<<"Element doesn't exist in the array!"<<endl;
else
cout<<"Element found at the index "<<foundAt<<endl;
}
Output:
Element found at the index 4Here, we can see that the array in which we have to search for the given element is getting halved at each iteration. So, the time complexity of the binary search algorithm is O(log(N)), where 'N' is the number of elements in the array.
305+ registered