Binary Search: Practice Problems

Binary Search is a Divide and Conquer algorithm. Like all divide-and-conquer algorithms, binary search first divides a large array into two smaller subarrays and then recursively (or iteratively) operate the subarrays. But instead of operating on both subarrays, it discards one subarray and continues on the second subarray. This decision of discarding one subarray is made in just one comparison.

So binary search basically reduces the search space to half at each step. By search space, we mean the subarray of a given array where the target value is located (if present in the array). Initially, the search space is the entire array and binary search redefines the search space at every step of the algorithm by using the property of the array that it is sorted. It does so by comparing the mid-value in the search space to the target value. If the target value matches the middle element, its position in the array is returned. Otherwise, it discards half of the search space based on the comparison result.

In this post, we have listed out commonly asked interview questions that use binary search algorithm:

1. Binary Search Algorithm
2. Find the number of rotations in a circularly sorted array
3. Search an element in a circularly sorted array
4. Find the first or last occurrence of a given number in a sorted array
5. Count occurrences of a number in a sorted array with duplicates
6. Find the smallest missing element from a sorted array
7. Find floor and ceil of a number in a sorted integer array
8. Search in a nearly sorted array in logarithmic time
9. Find the number of 1’s in a sorted binary array
10. Find the peak element in an array
11. Find the missing term in a sequence in logarithmic time
12. Find floor and ceil of a number in a sorted array (Recursive solution)
13. Find the frequency of each element in a sorted array containing duplicates
14. Find the square root of a number using a binary search
15. Division of two numbers using binary search algorithm
16. Find the odd occurring element in an array in logarithmic time
17. Find pairs with difference `k` in an array | Constant Space Solution
18. Find `k` closest elements to a given value in an array
19. Binary Search in C++ STL and Java Collections
20. Ternary Search vs Binary search
21. Exponential search
22. Unbounded Binary Search