Binary Search is a Divide and Conquer algorithm. Like all divide and conquer algorithms, Binary Search first divides a large array into two smaller sub-arrays and then recursively (or iteratively) operate the sub-arrays. But instead of operating on both sub-arrays, it discards one sub-array and continue on the second sub-array. This decision of discarding one sub-array is made in just one comparison.
So Binary Search basically reduces the search space to half at each step. By search space we mean sub-array of given array where the target value is located (if present in the array). Initially, the search space is the entire array and binary search redefine 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 else it discards half of the search space based on the comparison result.
In this post, we have list out commonly asked interview questions that uses binary search algorithm –
Thank you for being with us. 🙂