Binary Search

Question 1

Search in bitonic array

Given a bitonic sequence of distinct elements, find given element in logn time.

Answer 1

A bitonic sequence is one which is first strictly increasing and then after a point strictly decreasing.
So first find the peak element, using binary search and the fact that it will be greater than the element to its left but smaller than the element to its right. There will be only one such element.
Once you have the peak element then you have an increasing sequence and a decreasing sequence.
Using binary search, search for the element in the two sorted arrays .

Question 2

Smaller or equal elements

Find the rightmost index of the given element, except that it should return the closest smaller no. if x is not present.

Answer 2

If (l<=h) return l and not -1. This is for the case when x is not present and we have to return the closest smaller.
The array can have repeated elements. To ensure that we are returning the rightmost occurence, on finding x, we additionally also confirm that it is not equal to the element on its right.
If arr(mid) <=x then l becomes mid+1
( Not just

Question 3

Wood cutting made easy
Ojas sets a height parameter and the machine raises a giant sawblade to that height and cuts off all tree parts higher than h. Ojas then takes the parts that he cut off. Find the maximum integer height h, that allows ojas to cut off at least b meters of wood.

Answer 3

Observe that you have to search for optimal height. So this is bs in h.
You can do bs in h and for every mid calculate the wood obtained. If the wood obtained is less, then you will have to decrease the height. So end =mid. Else if would obtained is greater then increase height , start =mid+1.
But this solution fails in tc as calwood is O(n) time.

l=1 and h = some very big number
While (l

Question 4

Matrix search
Given a matrix of size nxm and an integer write an efficient algorithm that searches for b in it. Integers in each row are sorted from left to right
The first integer of each row is greater than or equal to the last integer of the previous row

Answer 4

Since elements in a row are sorted and the first element in a row is greater than or equal to the last element in the previous row, we will first find the row in which the element might be present using binary search.
We consider the first column (0 index) and find the largest smaller element. That would give us the row in which the given element might be present.
Now that we know the row, and elements of a row are sorted, we can apply bs only on that row and find the column index.

Question 5

Search for a range

Given a sorted array of integers, find the starting and ending indices of the given element.

Answer 5

Find the rightmost index using bs
Similarly find leftmost index. Return
Simple!

Question 6

Sorted insert position
Given sorted array a and target b, return index of target is found. Else return index where it would be if it were inserted inorder

Answer 6

Again, we need to find the largest smaller element using binary search.
Be careful of corner cases. If n=1 then check if a[0] >= x then return 0 as the element if not present and is greater than x, x would be inserted before it. So at index 0 and the one present would be at index 1. Else 1

Now if size greater then one we need to find largest smaller number.
If element is present, the return it’s index.
While l

Question 7

Matrix median

Given a matrix in which each row is sorted, find and return the overall median of the matrix.

Answer 7

Intialize l=1 and h= big number
Then while l< h for every mid, we try to check if mid is our median.
For this, we need to count the number of elements in the matrix which are smaller than or equal to mid. We do this by counting the number of elements smaller than or equal to in each row
For mid to be median, this number should be nxm /2
If it is smaller then, median should be increased. So l = mid+1
Else h= mid-1
Return low.

To find the number of elements smaller than or equal to mid in a given row, we again make use of bs.
We just have to find the index of mid or largest smaller element.
If row[mid]<= median
Low= mid+1
Else
High = mid-1

Return l

Question 8

Square root of an integer

Answer 8

Start=1 end=x
If(mid*mid) ==x
Return mid

Question 9

Allocate books
A books with number of pages in the ith book= a[i]. There are b students.
A book will be allocated to exactly one student.
Each student needs atleast one book
Allotment of books needs to be contiguous
Allocate such that maximum number of pages alloted to a student is minimum.

Answer 9

Hat is the minimum answer possible and what is the maximal answer possible to this question?
Minimal maximum which can be possible is the minimum number in the entire array.
// 12 12 12 12 students=4 then minimal maximal =12

Maximum possible answer can be the sum of all the elements in the array. Eg say students=1
Our and is going to lie somewhere between these 2
Low is minimum number
High is sum of array
Find mid. Say we want mid to be our answer
We keep adding pages to first student. When they exceed the mid, then we add another student and start allocating to him and so on.
So by keeping mid as the barrier we check how many students we need . If it exceeds the given number of students, then obviously by decreasing the barrier further, we would need more Student as each student now can hold lesser number of pages. So if the number of students exceeds, then we increase low to mid +1
If students = given, then it could be one of our possible answer. All higher barriers will also not exceed the number of students. But we want the minimal. So the space from mid+1 to high gets eliminated.
High = mid-1
Res= min(res,mid)
When low becomes greater than high , return res

Question 10

Median of two sorted arrays

Answer 10

Take adv of the fact that half ofthe total number of elements in both the arrays will be present on side of the median, nd the others on the other half.
We pick those number of elements from array 1 and 2. We need to check if the picked left half is a valid one or not. To check if we have ucked the correct left half, all the elements on the left half must be smaller than all elements on the right half.
Check for cross ones
Left1 left2 right1 right 2
Median will be max(left1, left2) + min(right1, right2) by 2 will be our median.to check for vaodity, L1<=R2 and l2 <=r1
We are going to use binary search to find the partition
Int low=0 and high= m
Cut1 = low + high /2
Cut2 will be median position -cut1
( Median position gives us the number of elements that should be present on the left half)

If L1 >R2 opposite of what we want, that means that we need to decrease R1. So high is cut-1
Else low is cut+1