What is Binary Search?
Before moving ahead, you must be familiar with Linear Search algorithm.
In Linear Searching, we have to search an element in an array irrespective of it being sorted or unsorted. The time complexity of this algorithm is O(n), where n is the size of array. But what if we have a sorted array? Can we improve the complexity?
The answer is YES and the solution is Binary Search. This algorithm allows us to search an element in O(log n) time.
Problem Statement : Search an element in a sorted array of size n.
Approach : There are two approaches to solve this problem. One of them is Linear Search (which you already know) and the other one is Binary Search (which we’ll be discussing below).
The basic idea behind this algorithm is to divide the problem in two halves and discard one of them at each iteration. So firstly, we choose a starting point and an ending point of the array i.e start = 0 and end = n-1. Then we find its mid i.e mid = (start + end) / 2. Now the array is divided in two halves and we’ve three areas to compare with. At first we’ll compare the element to be searched with the element at mid. If it matches, we’ll return mid otherwise, we’ll search either towards its left or towards its right. Now we should have a criteria to decide the part to be traversed further. Since its a sorted array, its evident that the left part will contain all the elements smaller than that and right part will contain all the elements greater than that. Keeping this in mind, we can move to left if the element to be searched is smaller than the element at mid or move to right if the element to be searched is greater than the element at mid. This process will continue until the starting point exceeds the ending point.
I hope you’ve got the basic idea of how binary search algorithm works. This is a very important algorithm for competitive programming and interviews. There are a plenty of problems based on binary search.
For more problems on binary search, visit “How to identify a Binary Search Problem?”.
All the best peeps! Keep Coding! ❤
