Binary Search

Question 1

Initial bounds of Binary Search

Answer 1

l = 0 and r = n - 1

If the value can be inserted at the end, r = n

Question 2

Calculate Midpoint of Binary Search bound

Answer 2

int m = l + (r - l)/ 2;
Rather than
int m = (l + r) / 2
to avoid overflow

// when odd, return the only mid
// when even, return the lower mid
int mid = lo + ((hi - lo)/2);

// when odd, return the only mid
// when even, return the upper mid
int mid2 = lo + ((hi - lo + 1) / 2);

Question 3

infinite While Loop for lower mid

Answer 3

// ❌ The following code results in inifite loop
let mid = lo + ((hi - lo)/2); // aka the lower mid
// We should use:
// let mid = lo + ((hi - lo + 1)/2) // aka the upper mid

if (100% sure logic) {
right = mid - 1
} else {
left = mid // <– note here
}

Consider when there’s only 2 elements left, if the if condition goes to the else statement, since left = mid, our left boundary will not shrink, this code will loop for ever. Thus, we should use the upper mid.

Question 4

Infinite While Loop for upper mid

Answer 4

// ❌ The following code results in inifite loop
let mid = lo + ((hi - lo + 1)/2); // aka the upper mid
// We should use:
// let mid = lo + ((hi - lo)/2) // aka the lower mid

if (100% sure logic) {
left = mid - 1;
} else {
right = mid // <– note here
}

Consider when there’s only 2 elements left, if the if condition goes to the else statement, since right = mid our right boundary will not shrink, this code will loop for ever. Thus, we should use the lower mid.

Question 5

Basic Binary Search Implementation (js)

Answer 5

var search = function(nums, target) {
let lo = 0, hi = nums.length-1;
while (lo < hi) {
let mid = lo + Math.floor((hi-lo+1)/2);
if (target < nums[mid]) {
hi = mid - 1
} else {
lo = mid;
}
}
return nums[lo]==target?lo:-1;
};

Or Use Lower Mid
while (lo < hi) {
let mid = lo + Math.floor((hi-lo)/2);
if (target < nums[mid]) {
hi = mid
} else {
lo = mid + 1;
}
}

Question 6

Binary Search Loop condition

Answer 6

Always use while (lo < hi) so we know that when the loop breaks low = high

Question 7

Post processing

Answer 7

At the end, we need to check the last element: nums[l/r] which has not been checked in binary search loop with target to determine the index. We call it the post processing.

Question 8

Basic Binary Search Checking MidPoint as well

Answer 8

int left = 0;
int right = array.Length -1;

while (left <= right)
{
int mid = left + (right - left) / 2;

if(array[mid] == value)
	return mid;
else if(array[mid] < value)
	left = mid + 1;
else
	right = middle -1; }

return -1;

Question 9

Search or Insert Binary Search code

Answer 9

public int searchInsert(int[] nums, int target) {
int pivot, left = 0, right = nums.length - 1;
while (left <= right) {
pivot = left + (right - left) / 2;
if (nums[pivot] == target) return pivot;
if (target < nums[pivot]) right = pivot - 1;
else left = pivot + 1;
}
return left;
}