Ace The Binary Search

Binary Search

What is binary search?

Binary search begins by comparing the middle element of the list with the target element. If the target value matches the middle element, its position in the list is returned. If it does not match, the list is divided into two halves.

Time and Space Complexities :

  • Best Time Complexity: O(1)
  • Average Time Complexity: O(log n)
  • Worst Time Complexity: O(log n)
  • Best Space Complexity: O(1)-0

Pseudo code for binary search:

BinarySearch(array, target):
{
left = lowestBound(array)
right = highestBound(array)

WHILE (left <= right)
{
middle = (left + right) / 2
if(target = array[middle])
RETURN middle
else if(target < array[middle])
right = middle - 1
else
left = middle + 1
}
RETURN -1
}

Example:

Consider the following list of 5 numbers: 21, 22, 23, 24, 25. We need to find whether number 25 is present in the list or not.

Beyond Sorted Array Binary Search

Binary search obviously works on searching for elements in a sorted array. But if you think about the reason why it works is because the array itself is monotonic ( either increasing or decreasing ). So, if you are a particular position, you can make a definite call whether the answer lies in the left part of the position or the right part of it.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store