Binary search

Binary search
So when do u do start<end or start<=end and when to left=mid or left=mid+1 and same for right?

Template 1 that i have seen but i didnt really use:

start<=end
left=mid+1
right=mid-1

Template 2 by this leetcode:
https://leetcode.com/discuss/general-discussion/786126/Python-Powerful-Ultimate-Binary-Search-Template.-Solved-many-problems

a very importnat thing is to put condition for finding the upper half (right=mid) because then, left variable is gauarnteed to be the minimal value that satisfies that condition.

start<end
left=mid+1
right=mid

At the end of search, left is the minimal value that satisfies the condition.

look at https://velog.io/@whitehousechef/%EB%B0%B1%EC%A4%80-16401%EB%B2%88-%EA%B3%BC%EC%9E%90-%EB%82%98%EB%88%A0%EC%A3%BC%EA%B8%B0

and
https://velog.io/@whitehousechef/Leetcode-875.-Koko-Eating-Bananas

Also, left_idx = bisect_left(lst, target) might come in handy like in this q.
https://velog.io/@whitehousechef/%EB%B0%B1%EC%A4%80-10816%EB%B2%88-%EC%88%AB%EC%9E%90-%EC%B9%B4%EB%93%9C-2

BUT not always this template

So the above template of left=mid+1, right and mid = left+(right-left)//2 is cases when

• Finding if a value exists in a sorted array
• Finding the first position where a condition becomes true
• Finding the minimum valid value that satisfies a condition

But there is another case where u want to find the MAXIMUM valid value.

In this kind of case we use this template to maximise our search

left, right = min_possible, max_possible
while left < right:
    mid = (left + right + 1) // 2  # Ceiling division
    if is_valid(mid):
        left = mid  # Try to find even larger valid values
    else:
        right = mid - 1  # This value is too large
return left

index out of range?

https://velog.io/@whitehousechef/Leetcode-162.-Find-Peak-Element

examples

Minimize the Maximum Difference of Pairs
House Robber IV
Maximum Candies Allocated to K Children
Maximum Value at a Given Index in a Bounded Array
Kth Missing Positive Number
Minimum Number of Days to Make m Bouquets
Find the Smallest Divisor Given a Threshold
Divide Chocolate
Capacity To Ship Packages In N Days
Koko Eating Bananas
Minimize Max Distance to Gas Station
Split Array Largest Sum