Table of contents
- Abstract
- Introduction
- How to identify a binary search problem?
- Problem -1:
- Implementation in C++
- Implementation in Java:
- Implementation in Python
- Time and Space Complexity
- Problem-2:
- Implementation in C++
- Implementation in Java
- Implementation in Python
- Time and Space Complexity:
- Problem-3:
- Defining the predicate function:
- Implementation in C++
- Implementation in Java
- Implementation in Python
- Practice Problems to get in shape
Abstract
Binary search is a very common and widely used strategy for solving many algorithmic problems. The problems around binary search are common in tech interviews as well as programming contests. There are numerous applications of this algorithm some of them include searching for an element in a sorted arrangement, finding the frequency of an element in a sorted sequence, finding the first and last occurrence of an element in a sorted sequence, checking whether n is a square of an integer or not to name a few.
All of the above-mentioned problems have one thing in common and that is their monotonic behavior and in this article, we shall learn to identify these monotonic patterns of the problems. Let's delve into the process.
Introduction
Binary search is made up of two words binary means "2" and search means to look for something. Let's take an example of searching for a word in a physical dictionary, to search for a word in the dictionary we open it in the middle and pick a random word from it then if your word starts with R and the picked word starts with Q, then it is explicit that we shall not find our target word in the first half of the dictionary and hence we move to the second half of it to search for our word. Then we again open the dictionary in the middle of the second half and repeat the process. In this way each time we look for a word we are reducing the search space by half and hence reducing the extra work of naive searching just because we have a pattern in our dictionary that the words are written in alphabetical order.
Let's ask ourselves, how many checks we need to perform to get to the desired word, suppose we had n pages in the dictionary, then each time the search space is reduced to half i.e.
n reduced to n/2
n/2 reduced to n/4
n/4 reduces to n/8
and so on
The process will stop say after k matches when we find our desired word then we can write it as
$$\begin{align} n/2^k = 1 \\ n = 2^k \\ log2(n) = k \\ \end{align}$$
Hence, for a dictionary of size 1000 pages, it would take us only log2(1000) which is approximately 10 matches which is far better than going through every page.
How to identify a binary search problem?
The very first step to solving a binary search problem is to identify if it is a binary search problem or not. The only criterion for that is to look for monotonic behavior in whatever situation we are given. we know that a monotonic function is ever increasing or decreasing function and we need to figure out the quantity which is showing this type of behavior in the problem statement.
Let's better understand the above idea using some examples
Problem -1:
Given a sequence of integers sorted in ascending order, find the target element in it.
Let's start by identifying the monotonicity, we can observe that the integers are sorted in ascending order which means the integers are ever-increasing i.e. monotonic.
Here, we can see that we took 3 checks to find the target element in the array using binary search.
Following are the steps to perform the above procedure:
Define the search domain, [1, n] in this case.
Initialize two pointers left = 0 and right = n-1 to mark both ends of the domain.
While we have a non-zero domain i.e. [left, right] or till left <= right, find the middle element as middle = (left + right)/2 and check for the element at this middle index.
If the element at the middle index is equal to the target element, in that case, return that element.
If the element at the middle index is greater than the target element, in that case, discard the right subarray i.e. [middle+1, n-1] and reinitialize right = middle.
Otherwise, discard the left subarray i.e. [left, middle] and reinitialize left = middle+1.
Finally, If I do not find the element at any position in the array then we return -1 as the default value.
Let's see the implementation:
Implementation in C++
#include<bits/stdc++.h>
using namespace std;
//Function to perform binary search
int binarySearch(int left, int right, int arr[], int target){
//Base case
if(left < right)return -1;
//Repeat till we have a positive search domain.
while(left < right){
//find the middle element
int middle = left + (right - left)/2;
//check if the middle element is
// the target element
if(arr[middle] == target)return arr[middle];
//if the middle element is greater than target
// element
if(arr[middle] > target){
right = middle;
}else{
left = middle-1;
}
}
//Otherwise return -1
return -1;
}
Implementation in Java:
import java.util.*;
class Main {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
int target = 4;
int result = binarySearch(0, arr.length, arr, target);
if (result == -1) {
System.out.println("Element not found");
} else {
System.out.println("Element found: " + result);
}
}
//Function to perform binary search
public static int binarySearch(int left, int right, int[] arr, int target){
//Base case
if (left >= right) {
return -1;
}
//Repeat till we have a positive search domain.
while (left < right) {
//find the middle element
int middle = left + (right - left) / 2;
//check if the middle element is
// the target element
if (arr[middle] == target) {
return arr[middle];
}
//if the middle element is greater than target
// element
if (arr[middle] > target) {
right = middle;
} else {
left = middle + 1;
}
}
//Otherwise return -1
return -1;
}
}
Implementation in Python
# Function to perform binary search
def binarySearch(left, right, arr, target):
# Base case
if left >= right:
return -1
# Repeat till we have a positive search domain.
while left < right:
# find the middle element
middle = left + (right - left) // 2
# check if the middle element is
# the target element
if arr[middle] == target:
return arr[middle]
# if the middle element is greater than target
# element
if arr[middle] > target:
right = middle
else:
left = middle + 1
# Otherwise return -1
return -1
Time and Space Complexity
We can see that the search space is divided into half of the initial one each time we check for an integer and hence, the time complexity is log2(N) as we discussed earlier while the space complexity is O(1) i.e. constant because we are not using any extra space.
Problem-2:
Given a sequence of integers sorted in increasing order, find the position of the first appearance of the target element in the range [first, last).
Let's start by identifying the monotonicity, we can observe that the integers are sorted in ascending order and the same integers appear adjacent to each other which means the integers are ever-increasing i.e. monotonic.
In the above procedure, we performed the binary search to find the first occurrence of the element 6
Let's see the implementation of the above procedure
Implementation in C++
#include<bits/stdc++.h>
using namespace std;
//first occurence of an element
int firstOccurence(int arr[], int lo, int hi, int target){
if(lo <= hi){
int mid = lo + (hi - lo)/2;
if((mid == 0 || arr[mid-1] > x) and arr[mid] == x)
return mid;
else if(target > arr[mid])
hi = mid + 1;
else
lo = mid - 1;
}
return -1;
}
int main(){
int arr[] = {1, 2, 2, 2, 2, 3, 4, 7, 8, 8};
int n = sizeof arr / sizeof arr[0];
target = 8;
cout << "First occurence of the " << target << " is" << firstOccurence(arr, 0, n-1, target);
}
Implementation in Java
import java.util.*;
public class Main {
//first occurrence of an element
static int firstOccurrence(int[] arr, int lo, int hi, int target){
if(lo <= hi){
int mid = lo + (hi - lo)/2;
if((mid == 0 || arr[mid-1] < target) && arr[mid] == target)
return mid;
else if(target > arr[mid])
lo = mid + 1;
else
hi = mid - 1;
}
return -1;
}
public static void main(String[] args) {
int[] arr = {1, 2, 2, 2, 2, 3, 4, 7, 8, 8};
int n = arr.length;
int target = 8;
System.out.println("First occurrence of " + target + " is " + firstOccurrence(arr, 0, n-1, target));
}
}
Implementation in Python
# first occurrence of an element
def first_occurrence(arr, lo, hi, target):
if lo <= hi:
mid = lo + (hi - lo) // 2
if (mid == 0 or arr[mid-1] < target) and arr[mid] == target:
return mid
elif target > arr[mid]:
lo = mid + 1
else:
hi = mid - 1
return -1
arr = [1, 2, 2, 2, 2, 3, 4, 7, 8, 8]
n = len(arr)
target = 8
print("First occurrence of", target, "is", first_occurrence(arr, 0, n-1, target))
Time and Space Complexity:
We can see that the search space is divided into half of the initial one each time we check for an integer and hence, the time complexity is log2(N) as we discussed earlier while the space complexity is O(1) i.e. constant because we are not using any extra space.
Problem-3:
You are given an integer array of heights representing the heights of the building, some bricks and some ladders.
You start your journey from building 0 and move to the next building by possibly using bricks or ladders.
While moving from building I to i+1 (0-indexed)
If the current building's height is greater than or equal to the next building's height, you do not need a ladder or bricks.
If the current building's height is less than the next building's height, you can either use one ladder or h[i+1] - h[i] bricks.
Return the furthest building index (0-index) you can reach if you use the given ladders and bricks optimally.
Example
Here, I have input array of heights as heights[] = {4, 2, 7, 6, 9, 11, 14}, and bricks = 5, ladders = 1.
Let's see where we land starting from the first building i.e. building number 0, we can simply jump to building 1 without using any bricks or ladders because building number 1 has a smaller height than building number 0 after that to jump to building number 2 which has a height of 7 units we require 5 bricks or 1 ladder which one to choose, let's choose bricks and consume all bricks to jump to building number 2, then we jump to building number 3 without requiring bricks or ladder, then we again have a building with greater height since we are left with 0 bricks and 1 ladder we can use a ladder to jump to building number 4 and we consume all ladders and bricks here, the path taken is shown below
Let's ask ourselves can we do better or we can reach even the next buildings by changing the moves which I took here let's see
Another option would be to choose the ladder for the first jump that is from building 1 to building 2 and then use 3 bricks to move from building 3 to 4 and finally use the remaining 2 bricks to jump to building 5. Using this approach we reach building number 5 at the end which is a better answer.
So, how do we decide which moves to make, well we can observe that in the second case what we did is simply replaced the jump till building number 3 which consumed a maximum number of bricks with a ladder hence optimizing the number of bricks which were used further to jump to next buildings.
At the end of the day we just need to optimize the number of bricks we consume i.e. try to consume bricks for smaller jumps and larger jumps and try to use a ladder, in this way, I will be going relatively far.
How all this is related to the binary search let's understand that.
To perform the binary search we require a monotonic behavior in the problem, here observe the indices
Here, the monotonicity is observed in indices, let's take an index I and ask ourselves if it is reachable, if it can be then all indices before I are also reachable till index 0.
Let's define a predicate function isReachable(index) which returns true if the index passed can be reached or not otherwise it returns false.
Now, the problem reduces to returning the last index where the function isReachable(index) returns true which can be simply obtained by performing a binary search over the indices.
Defining the predicate function:
So, how do we define our predicate function, we know that we need to use the ladders for the jumps with maximum length or height difference and others we may use bricks if available.
Therefore, simply store all differences in heights of consecutive buildings and use ladders for all the larger differences till I consume all ladders and finally use bricks for the remaining jumps I can make.
Let's see the implementation of the idea explained above:
Implementation in C++
class Solution {
public:
bool check(vector<int> heights, int bricks, int ladders, int mid){
vector<int> diff;
for(int i = 1; i <= mid; i++){
if(heights[i] > heights[i-1]){
diff.push_back(heights[i]-heights[i-1]);
}
}
sort(diff.begin(), diff.end(), greater<int>());
int l = diff.size();
for(int i = ladders; i < l; i++){
if(diff[i] > bricks) return false;
bricks -= diff[i];
}
return true;
}
int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
int n = heights.size();
int lo = 0, hi = n-1;
while(lo < hi){
int mid = (lo+hi+1)/2;
if(check(heights, bricks, ladders, mid)){
lo = mid; // if true, then binary search on right half
}
else{
hi = mid-1; // if false, then binary search on left half
}
}
return lo;
}
};
Implementation in Java
import java.util.*;
class Solution {
boolean check(ArrayList<Integer> heights, int bricks, int ladders, int mid) {
ArrayList<Integer> diff = new ArrayList<Integer>();
for (int i = 1; i <= mid; i++) {
if (heights.get(i) > heights.get(i-1)) {
diff.add(heights.get(i) - heights.get(i-1));
}
}
Collections.sort(diff, (a,b) -> b-a);
int l = diff.size();
for (int i = ladders; i < l; i++) {
if (diff.get(i) > bricks) return false;
bricks -= diff.get(i);
}
return true;
}
int furthestBuilding(ArrayList<Integer> heights, int bricks, int ladders) {
int n = heights.size();
int lo = 0, hi = n-1;
while (lo < hi) {
int mid = (lo+hi+1) / 2;
if (check(heights, bricks, ladders, mid)) {
lo = mid;
} else {
hi = mid-1;
}
}
return lo;
}
}
Implementation in Python
from typing import List
class Solution:
def check(self, heights: List[int], bricks: int, ladders: int, mid: int) -> bool:
diff = []
for i in range(1, mid+1):
if heights[i] > heights[i-1]:
diff.append(heights[i]-heights[i-1])
diff = sorted(diff, key=lambda x: -x)
l = len(diff)
for i in range(ladders, l):
if diff[i] > bricks:
return False
bricks -= diff[i]
return True
def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
n = len(heights)
lo, hi = 0, n-1
while lo < hi:
mid = (lo+hi+1) // 2
if self.check(heights, bricks, ladders, mid):
lo = mid
else:
hi = mid-1
return lo
Check out my video for this problem:
Practice Problems to get in shape
So that's all I have got in this blog, I appreciate your patience till now, If you liked the blog then stay tuned for more such relevant content.
I will see you soon :D