Difficulty: Easy, Asked-in: Google, Amazon, Adobe, Oracle, Qualcomm, SAP Labs
Given a sorted array X[] of n elements, search a given element key in X[]. If the key exists, then we need to return its index in the sorted array. Otherwise, return -1.
Examples
Input: X[] = [-4, 2, 4, 5, 9, 12], key = 5, Output: 3
Explanation: 5 exists in X[] and its index is 3. So we return 3.
Input: X[] = [-4, 2, 4, 5, 9, 12], key = 6, Output: -1
Explanation: 6 does not exist in x[] so we return -1.
Let's imagine a game where the computer selects a number between 1 and 16, and we need to find this number with a minimum number of guesses. The computer tells us whether the guessed number is equal to, greater, or less than the actual number for each guess.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
The linear guess of all the continuous values 1, 2, . . . 16 is inefficient because, with each question, we eliminate one number only. In the worst-case scenario, we need to guess 16 times! But our aim is to find the number with a minimum number of guesses. so what would be the best guess at the start?
Here is an idea: numbers are given in sorted order, so the best first guess would be to choose the middle number (which is 8 here) and reduces the set of numbers by half in one go. Think!
After every guess, we reject half of the given numbers in one go. This is a significant improvement where we are decreasing the input size by a factor of 1/2. So what would be the minimum number of guesses required in the above problem? It's an exercise for you to think about!
The binary search algorithm is a fundamental problem to understand the divide and conquer approach: dividing a given problem into smaller sub-problems, solving each sub-problems recursively, and combining the sub-problem's solutions to obtain a solution to the original problem. But how do we apply the divide and conquer approach? Let's think!
We recursively search until the key is found (successful search) or the subarray size is equal to 0 (unsuccessful search). The core idea is: At each stage of recursion, we have only one sub-problem and we search the key in the array by continuously dividing the search interval in half.
Suppose we use a function binarySearch(X[], l, r, key) to search the given value key in the sorted array. Here we are using two variables, l and r as the index of the left and right end of the subinterval in the array X[]. We start with l = 0 and r = n-1.
Divide part
Conquer part
If the middle element is greater than the key, then the key must not be present in the right half of the array, or in other words: we recursively search the key in the left half of the array.
if (X[mid] > key)
return binarySearch(X, l, mid - 1, key)
If the middle element is smaller than the key, then the key must not be present in the left half of the array, or in other words: we recursively search the key in the right half of the array.
if (X[mid] < key)
return binarySearch(X, mid + 1, r, key)
Combine part
This is a trivial step because, after comparing the middle element, one sub-problem solution (either left or right) will return the index if the key is present in the array. No need to combine the solution of the sub-problems! Think!
Binary search base case
The base case would be the scenario when the left index crosses the right index and the subarray shrinks to zero i.e. if (l > r), return -1. This is the case of an unsuccessful search when the key is not present in the array. In other words, this would be the last stage of the recursion or the smallest version of the sub-problem!
Recursive binary search pseudocode
Binary search is easy to visualize using recursion. But can we implement the above code using iteration or loop? Let’s think! If we observe closely, only two parameters get updated during every recursive call: the left and right index. In other words, we need to find a way to update the left and right index of the current sub-array in a loop. Here is the idea:
If the middle element is greater than the key, we need to search the key in the left half of the array. For the left array, the left index would be the same, but the right index would be mid - 1.
if (X[mid] > key)
r = mid - 1
If the middle element is smaller than the key, we need to search the key in the right half of the array. For the right array, the right index would be the same, but the left index would be mid + 1.
if (X[mid] < key)
l = mid + 1
Pseudocode of iterative binary search
After each comparison in the algorithm, the size of the input decreases by half. Worst case situation would be an unsuccessful search, i.e. when we reach the base-case situation. Initially, we have n elements, then n/2 elements after the first step, n/4 elements after the second step, and so on, we will reach the case of a single element array.
=> n -> n/2 -> n/4 -> …… 1 -> unsuccessful search
Suppose we reach the base case after k steps.
=> n/2^k = 1 => n = 2^k => k = log2n
So, binary search time complexity = O(logn)
Another idea of analysis !
For the clear picture, let’s assume for the moment that the size of the array is a power of 2 (n = 2^k => k = log2n). Now each time when we compare the middle element, we cut the size of the subarrays to search by half.
Binary search analysis using master theorem
Let’s assume that T(n) is the worst-case time complexity of the binary search for n elements. When we have n>0, then we can break down the time complexities as follows —
For calculating the T(n), we need to add the time complexities of the divide, conquer, and combine part => T(n) = O(1) + T(n/2) + O(1) = T(n/2) + c. Here is the recurrence relation of the worst-case time complexity:
This recurrence relation is in the form T(n) = aT(n/b) + O(n^k) where a≥1 and b>1. We can think to apply the master theorem! There are the three cases of the solution via master theorem:
If we compare the recurrence relation of binary search and master theorem
a = 1, b = 2 where both a≥1 and b>1
=> f(n) = c = cn^0 = O(n^0) => k = 0
=> Similarly, logb(a) = log 2(1) = 0 => Hence, logb(a) = k = 0
So binary search recurrence satisfy the 2nd case of the master theorem. Time complexity T(n) = O(n^k logn) = O(n^0 logn) = O(logn)
The space complexity of the binary search depends on the implementation. In the iterative approach, we use constant extra space so that the space complexity would be O(1). In the recursive method, space complexity depends on the size of the recursion call stack.
Here is a note by Jon Bentley about binary search from the book Programming Pearls:
I’ve assigned binary search in courses at Bell Labs and IBM. Professional programmers had a couple of hours to convert its description into a program in the language of their choice; high-level pseudocode was fine. At the end of the specified time, almost all the programmers reported that they had the correct code for the task. We would then take thirty minutes to examine their code, which the programmers did with test cases. In several classes and with over a hundred programmers, the results varied little: ninety percent of the programmers found bugs in their programs (and I wasn’t always convinced of the correctness of the code in which no bugs were found). I was amazed: given ample time, only about ten percent of professional programmers were able to get this small program right. But they aren’t the only ones to find this task difficult: in Section 6.2.1 of his Sorting and Searching history, Knuth points out that while the first binary search was published in 1946, the first published binary search without bugs did not appear until 1962.
Enjoy learning, Enjoy coding, Enjoy algorithms!
Subscribe to get well-designed content on data structures and algorithms, machine learning, system design, oops, and mathematics. enjoy learning!
Hashing is an effcient searching technique that maps keys and values into the hash table using a hash function. Explore this blog to learn: how do we perform hash mapping in data structures? How do hash maps work? What are some popular hash functions in programming?
EnjoyAlgorithms
Write a program to detect the loop in a linked list. A linked list with a cycle causes iteration over the list to fail because the iteration will never reach the end of the list. Therefore, it is desirable to be able to detect that a linked list has no cycle before trying an iteration. So, we are going to discuss various algorithms to detect a loop in a singly linked list. This is also one of the best-linked list interview problems.
EnjoyAlgorithms
