Binary search cheat sheet for coding interviews.
Published in
5 min readApr 2, 2020
This blog is a part of my “15 days cheat sheet for hacking technical interviews at big tech companies”. In this blog, we discuss the binary search in coding interviews.
Binary search algorithm
The basic idea of binary search is to search a given element x in a sorted array. The algorithm is based on divide and conquer technique. It repeatedly breaks down the array into two subarrays that may contain the item. It discards one of the subarray by utilising the fact that items are sorted. It continues halving the subarray until the value is found or the subarray is empty.
The time complexity is O(log n)
Limitations
- Binary search can only be applied when items are sorted. If the items are not sorted, we must sort them before applying the binary search. That will increase the total time complexity to O(n log n)
- Binary search can only be applied to data structures which allow direct access to the items. If we do not have direct access then we can not apply binary search on it eg. we can not apply binary search to Linked List.
