Binary Search Fundamentals
-
Algorithms and Data Structures: TheAlgorist.com
-
System Design: DistributedComputing.dev
-
Low Level Design: LowLevelDesign.io
-
Frontend Engineering: FrontendEngineering.io
জয় শ্রী রাম
🕉
If you already know the basics of Binary Search, feel free to skip to the next chapter Advanced Binary Search.
Binary Search is a very intuitive algorithm and I will show you how intuitive it is by giving an example. Say, you are teaching assistant for a class of 100 students who have Student IDs ranging from 1 to 100. The students appeared in their midterm exam and now they have been notified that their scores are out and they can visit the teaching assistant and take a look at their paper. The teaching assistant has arranged the students' papers in the ascending order of the Student IDs. Now say the student whose student id is 75 shows up and now you have to search his paper and hand that over to him so that he can see how his paper has been graded. If you are the teaching assistant you probably wouldn't go through all the papers sequentially from 1 to 75 to get the paper for the student with student id 75. What you would probably do is open the stack of papers to roughly through halfway (comparable to
mid in our code) through the papers and compare it. Let's suppose,
you saw that the student id was 50. You know that 75 comes after 50, so it must be in the second half of the stack.
So you take the second half of the stack (from student id 51 to 100 ) and treat it as its own little stack and repeat what you did before.
You picked up a paper which is roughly around midway and see what it's student id is and bingo it's 75. We would do the same thing
in our Binary Search algorithm and it will be clear in a minute when we look at its code below:
Iterative Solution:
public boolean binarySearchIterative(int[] searchSpace, int target) {
int left = 0;
int right = searchSpace.length - 1;
while (left <= right) { // it is very important to put <= and not just <
// otherwise your program will give wrong answer if the target
// happens to be the last element in the search space
// Take example of searchSpace = [1, 2, 3] and target = 3
// and see what would happen.
// right would be initialized as index 2 and left as 0 giving mid = 1
// searchSpace[1] = 2 which is < target value 3
// so right remains same but left becomes mid + 1 = 1 + 1 = 2
// now, mid = left + (right - left) / 2 = 2 + (2 - 2) / 2 = 2
// searchSpace[2] = 3 = target value. Returns true.
// So here the search would terminate when left = 2 and right = 2.
int mid = left + (right - left) / 2;
if (searchSpace[mid] == target) {
return true;
} else if (searchSpace[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return false;
}
Recursive Solution:
public boolean binarySearchRecursive(int[] searchSpace, int target) {
Arrays.sort(searchSpace); // do this only if it is not guaranteed that searchSpace is already sorted
return binarySearchRecursiveHelper(searchSpace, target, 0, searchSpace.length - 1);
}
private boolean binarySearchRecursiveHelper(int[] searchSpace, int target, int left, int right) {
if (left > right) {
return false;
}
int mid = left + (right - left) / 2;
if (searchSpace[mid] == target) {
return true;
} else if (searchSpace[mid] < target) {
return binarySearchRecursiveHelper(searchSpace, target, mid + 1, right);
} else {
return binarySearchRecursiveHelper(searchSpace, target, left, mid - 1);
}
}
Time Complexity:
Let's say we have a search space of n elements. In a single comparison, we have cut our search space to n / 2. Then with one more comparison we have cut it down to n / 4, and then in half and and half and half again and it goes on till the size of the search space becomes 1.
Step #1 n elements
|
|
v
Step #2 (n / 2) elements
|
|
v
Step #3 (n / 4) elements
|
|
v
Step #???? 1 element
The last element would be the element we are looking for. So how many steps does it take to reach 1 from n by dividing by 2 at each step ? If you are familiar with logarithm you would know that the answer is log2n.
If we can reach 1 from n by dividing by 2 in every step in a total of k steps, then that would mean if we would represent this as a tree then 2 would be the branching factor. Therefore, we would have 2 k = n
=> log2(2k) = log2n
=> k = log2n
From the above discussion it is clear that the time complexity is O(log2n), where n = total number of elements in the search space.
Problem Solving Using Binary Search Algorithm:
Problem#1: Search in Rotated Sorted Array with No Duplicates
Given an integer array nums sorted in ascending order, and an integer target.
Suppose that nums is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You should search for target in nums and if you found return its index, otherwise return -1.
All values of nums are unique.
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Example 3:
Input: nums = [1], target = 0
Output: -1
Solution:
Java Code and Algorithm:
Login to Access Content
Python Code and Algorithm:
Login to Access Content
Problem#2: Find Minimum in Rotated Sorted Array with Duplicates
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
Find the minimum element.
The array may contain duplicates.
Example 1:
Input: [1,3,5]
Output: 1
Example 2:
Input: [2,2,2,0,1]
Output: 0
Java Solution and Algorithm:
Login to Access Content
Python Solution and Algorithm:
Login to Access Content
Instructor:
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
