CODEWITHSUNDEEP
pythonalgorithm
Wizard
Wizard

Reputation: 22083

Binary search when terminating condition is `left < right`, step update is `left = mid +1, right = mid`

I was reading the Binary Search Template II in leetcode:

It is used to search for an element or condition which requires accessing the current index and its immediate right neighbor's index in the array.

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

I seems to me that the extra condition and nums[left] == target is unnecessary.

When changing:

if left != len(nums) and nums[left] == target:

to just:

if left != len(nums):

...it works perfectly:

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):
        return left
    return -1

Tests:

In [4]: nums = list(range(100))             

In [5]: binarySearch(nums, 55)              
Out[5]: 55

In [6]: binarySearch(nums, 101)             
Out[6]: -1

In [7]: binarySearch(nums, 38)              
Out[7]: 38

What's the reason nums[left] == target should be added?

Leetcode's summary on the template (for reference if you could not open its link):

Key Attributes:

  • An advanced way to implement Binary Search.
  • 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 [sic] Search Space is at least 2 in size at each step
  • Post-processing required. Loop/Recursion ends when you have 1 element left. Need to assess if the remaining element meets the condition.

Distinguishing Syntax:

  • Initial Condition: left = 0, right = length
  • Termination: left == right
  • Searching Left: right = mid
  • Searching Right: left = mid+1

Upvotes: 1

Views: 1699

Answers (3)

Javier Silva Ort&#237;z
Javier Silva Ort&#237;z

Reputation: 2982

First of all, when you change if left != len(nums) and nums[left] == target: to if left != len(nums): it seems to work fine because your tests are being made with nums = list(range(100)) which generates the integer sequence 0, 1, 2, ..., 99, as such, every index of nums is the same as its element, that is nums[i] == i. Without nums[left] == target you're actually returning the closest index to the index of your target element, and since with your test every index coincides with its element then it appears to give correct results but it's wrong. The nums[left] == target is the terminating condition that ensures that you actually found your target element in nums.

Upvotes: 0

Chris Happy
Chris Happy

Reputation: 7295

Test with nums = [9] and binarySearch(nums, 2). Assuming I understand the code properly, binary_search would return 0 as the "index" of the found item.

You need the last condition to ensure that you actually found the target element.

Otherwise, you're just finding a index for the item closest to the target in the array.

One more example:

IN nums = [1, 3, 4]

IN binary_search(nums, 2)
OUT 2 /* When 2 isn't in the array */

Upvotes: 0

mangusta
mangusta

Reputation: 3542

In contrast with canonical version of binary search where the loop terminates as soon as lo > hi is met, in this case the loop terminates when lo == hi. But since the element nums[lo] (which is also nums[hi]) has to be inspected as well, the additional check is added after the loop.

It is guaranteed that the loop terminates only and only when lo == hi, because moving left includes mid element in the future search (else: right = mid) while in canonical version, mid element is excluded from the future search in both cases

Upvotes: 2

Related Questions