Note

# Find the position where x should be inserted to maintain the sorted order of the array

# The left most
array.bisect_left(x)

# The right most
array.bisect_right(x)

Binary Search - A Different Perspective | Python Algorithms - YouTube

Types of questions

• Firstly see whether the range is [left, right] or [left, right) to determine the conditions

Find first or last of something

• Outer loop is still binary search, add additional logic when reach mid condition
  • See wether this mid is the first or last
    • If true, return it
    • Else, adjust the range

981. Time Based Key-Value Store
3152. Special Array II
2332. The Latest Time to Catch a Bus

Minimum in a sorted array

• Find whether the potential minimum is in left half or right half

while left < right:
		mid = left + (right - left) // 2
		if nums[mid] < nums[right]:
			right = mid
		else:
			left = mid + 1
			
	return nums[left]

154. Find Minimum in Rotated Sorted Array II

Find range of something

• 34. Find First and Last Position of Element in Sorted Array

1060. Missing Element in Sorted Array
1885. Count Pairs in Two Arrays
1552. Magnetic Force Between Two Balls
2055. Plates Between Candles
540. Single Element in a Sorted Array
852. Peak Index in a Mountain Array
1146. Snapshot Array
400. Nth Digit
729. My Calendar I
1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold