0%

BinarySearch

Posted on In

Binary Search Conclusion

Mr. Knuth, who invents KMP algorithm, once has said that the idea of binary search is straight forward, but devil in the details.

Basic binary search, only search for a value or an index

1
2
3
4
5
6
7
8
9
10
11
def binarySearch(nums, target):
    left, right = 0, len(nums)-1
    while left <= right:
        mid = left + (right-left) // 2
        if nums[mid] == target:
            return nums[mid]  # return mid
        elif nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
    return -1

Binary search for the left bound of an interval. [left, right]

1
2
3
4
5
6
7
8
9
10
11
12
13
def binarySearch(nums, target):
    left, right = 0, len(nums)-1
    while left <= right:
        mid = left + (right-left) // 2
        if nums[mid] == target:
            right = mid - 1
        elif nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
    if left >= len(nums) or nums[left] != target:
        return -1
    return left

Binary search for the right bound of an interval. [left, right]

1
2
3
4
5
6
7
8
9
10
11
12
13
def binarySearch(nums, target):
    left, right = 0, len(nums-1)
    while left <= right:
        mid = left + (right-left) // 2
        if nums[mid] == target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
        elif nums[mid] < target:
            left = mid + 1
    if right < 0 or nums[right] != target:
        return -1
    return right