Level 3

Binary Search

Binary search is the most efficient searching algorithm having a run-time complexity of O(log2 N). This algorithm works only on a sorted list of elements.

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. The first half consists of the first element to middle element whereas the second half consists of the element next to the middle element to the last element. 

Let's take an example and see how binary search works and number of steps it takes as compared to linear search.


Binary Search example

Important tutorials

1. Binary Search Implementations And Common Errors
View Tutorial
2. Beyond Sorted Array Binary Search
View Tutorial

Binary Search Problems

Search answer
Problem Score Companies Time Status
Matrix Median 225 76:37
Square Root of Integer 275 40:32
Allocate Books 350
Painter's Partition Problem 350 80:49
Simple binary search
Problem Score Companies Time Status
Matrix Search 250
Search for a Range 250
Sorted Insert Position 250
Search step simulation
Problem Score Companies Time Status
Implement Power Function 275
Simple Queries 300
Sort modification
Problem Score Companies Time Status
Median of Array 325 84:12
Rotated Sorted Array Search 325 56:53

Additional Practice

Problem Score Companies Time Status
WoodCutting Made Easy! 200 43:05
Search in Bitonic Array! 100 40:46