Binary Search Variations

First position of a repeated value

If a value appears several times, plain binary search stops at any copy. To find the first one, keep searching left even after a match:

def first_position(items, target):
    low, high = 0, len(items) - 1
    answer = -1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            answer = mid          # remember it...
            high = mid - 1        # ...but keep looking to the left
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return answer

print(first_position([1, 2, 2, 2, 3, 5], 2))

Output

1

Python's bisect module

bisect_left finds where a value would be inserted to keep the list sorted:

from bisect import bisect_left, bisect_right

nums = [1, 2, 2, 2, 3, 5]
print(bisect_left(nums, 2))     # first position of 2
print(bisect_right(nums, 2))    # just after the last 2
print(bisect_right(nums, 2) - bisect_left(nums, 2), "copies of 2")
print(bisect_left(nums, 4))     # where 4 would go

Output

1
4
3 copies of 2
5

Binary search on the answer

Binary search isn't only for lists. If the answer is a number and you can check “is this guess too big?”, you can binary search for it. Integer square root:

def int_sqrt(n):
    low, high = 0, n
    while low < high:
        mid = (low + high + 1) // 2
        if mid * mid <= n:
            low = mid            # mid works, maybe something bigger does too
        else:
            high = mid - 1       # mid is too big
    return low

print(int_sqrt(50))
print(int_sqrt(1000000))

Output

7
1000

Remember: Binary search needs a yes/no question whose answers go no, no, no, yes, yes, yes (or the other way). Then you can find where it switches in O(log n).