data structures

Question 1

binary search: l <= r

Answer 1

When the target is within the range of the numbers in nums, but it doesn’t exist in the list, the binary search loop will terminate when l > r. At that point:

r will be to the left of where the target would be inserted.
l will be to the right of where the target would be inserted

nums = [1, 3, 4, 6, 8, 9]
Case 1: target = 5
This target falls between 4 and 6. After the binary search:

l will be at the index of 6 (i.e., index 3).
r will be at the index of 4 (i.e., index 2).

f l >= len(nums), it means that the target is greater than all the numbers in the list nums.

Similarly, if r < 0, it would imply that the target is smaller than all the numbers in the list nums.

Question 2

binary search l < r vs l <= r loops:

Answer 2

while l <= r:

Suppose we have an array [1, 2, 3, 4, 5, 6], and we want to know if 5 is present. Using while l <= r, the loop will keep narrowing down the range until either the value is found or the range is empty.

while l < r:

Imagine you have a sorted array of binary values [0, 0, 0, 1, 1, 1], and you want to find the index of the first 1. Using while l < r, you can keep narrowing down the range until you’ve found the boundary between 0 and 1.

The crucial difference is the stopping condition. With while l <= r, you stop when the search space is empty. With while l < r, you stop when the search space is narrowed down to one possible candidate.

Question 3

review how to manipulate binary search to search for first and last occurences

Question 4

set: know the operations
- partition

Answer 4

and operation: &
union two sets: |=