Binary Search
Go to ProblemsBinary search is the most efficient searching algorithm having a run-time complexity of O(log2 N) in a sorted array.
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 the middle element whereas the second half consists of the element next to the middle element to the last element i.e. the search interval is repeatedly divided into halves.
Let's take an example and see how binary search works and number of steps it takes as compared to linear search.
Binary Search Problems
Simple binary search
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Search in Bitonic Array! | 100 |
|
53:22 | |
| Smaller or equal elements | 200 |
|
33:04 | |
| WoodCutting Made Easy! | 200 |
|
58:58 | |
| Matrix Search | 250 |
|
36:51 | |
| Search for a Range | 250 |
|
42:02 | |
| Sorted Insert Position | 250 |
|
25:03 |
Search answer
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Capacity To Ship Packages Within B Days | 200 |
|
47:08 | |
| Matrix Median | 225 |
|
77:24 | |
| Square Root of Integer | 275 |
|
40:32 | |
| Allocate Books | 350 |
|
68:01 | |
| Painter's Partition Problem | 350 |
|
81:38 | |
| Red Zone | 400 |
|
47:09 |
Search step simulation
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Implement Power Function | 275 |
|
59:44 | |
| Simple Queries | 300 |
|
67:04 |
Sort modification
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Median of Array | 325 |
|
87:06 | |
| Rotated Sorted Array Search | 325 |
|
56:53 |
