Binary Search advanced template explain

Question

I was learning the Binary Search template II on Leetcode. https://leetcode.com/explore/learn/card/binary-search/126/template-ii/937/

def binarySearch(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: int
    """
    if len(nums) == 0:
        return -1

    left, right = 0, len(nums)
    while left < right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid

    # Post-processing:
    # End Condition: left == right
    if left != len(nums) and nums[left] == target:
        return left
    return -1

It is said that key attributes of this template including

• Search Condition needs to access element's immediate right neighbor
• Use element's right neighbor to determine if condition is met and decide whether to go left or right
• Gurantees Search Space is at least 2 in size at each step

I didn't understand how the code "access element's immediate right neighbor" or use it to "determine if condition is met and decide whether to go left or right".

How does that work?

Answer 1

Yeah, the explanation is garbage. No wonder they hid the Binary Search section on the Explore page making it available via a direct link only, but maybe my comment will help someone.

As far as I understand, what they meant is, you can safely inspect the nums[mid + 1] element since the search space is guaranteed to be at least 2 in size. You can check out the official solution for the Find Minimum in Rotated Sorted Array problem (it's available without the Premium). The core idea there is to see if we are greater than the very next (mid + 1th) item, and I think this is the approach the 2nd template implies.

Beware though, there is a bug in the official solution (yeah, totally not cool), so refer to the discussion section if you decide to dive into this, there's a good post on it there.