Binary Search – Interview Questions and 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 AlgorithmEasy
2. Find the number of rotations in a circularly sorted arrayEasy
3. Search an element in a circularly sorted arrayMedium
4. Find the first or last occurrence of a given number in a sorted arrayEasy
5. Count occurrences of a number in a sorted array with duplicatesMedium
6. Find the smallest missing element from a sorted arrayMedium
7. Find floor and ceil of a number in a sorted integer arrayEasy
8. Search in a nearly sorted array in logarithmic timeMedium
9. Find the number of 1’s in a sorted binary arrayEasy
10. Find the peak element in an arrayMedium
11. Find the missing term in a sequence in logarithmic timeMedium
12. Find floor and ceil of a number in a sorted array (Recursive solution)Easy
13. Find the frequency of each element in a sorted array containing duplicatesEasy
14. Find the square root of a number using a binary searchEasy
15. Division of two numbers using binary search algorithmMedium
16. Find the odd occurring element in an array in logarithmic timeMedium
17. Find pairs with difference k in an array | Constant Space SolutionMedium
18. Find k closest elements to a given value in an arrayMedium
19. Binary Search in C++ STL and Java CollectionsBeginner
20. Ternary Search vs Binary searchBeginner
21. Exponential searchEasy
22. Unbounded Binary SearchEasy