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:
- Binary Search Algorithm
- Find the number of rotations in a circularly sorted array
- Search an element in a circularly sorted array
- Find the first or last occurrence of a given number in a sorted array
- Count occurrences of a number in a sorted array with duplicates
- Find the smallest missing element from a sorted array
- Find floor and ceil of a number in a sorted integer array
- Search in a nearly sorted array in logarithmic time
- Find the number of 1’s in a sorted binary array
- Find the peak element in an array
- Find the missing term in a sequence in logarithmic time
- Find floor and ceil of a number in a sorted array (Recursive solution)
- Find the frequency of each element in a sorted array containing duplicates
- Find the square root of a number using a binary search
- Division of two numbers using binary search algorithm
- Find the odd occurring element in an array in logarithmic time
- Find pairs with difference `k` in an array | Constant Space Solution
- Find `k` closest elements to a given value in an array
- Binary Search in C++ STL and Java Collections
- Ternary Search vs Binary search
- Exponential search
- Unbounded Binary Search