python Binary search It is surprisingly easy to implement bisect.bisect_left and bisect.bisect_right from 0

background

Binary search of python is usually implemented using the bisect library, but this time I tried using it from 0.

bisect.bisect_left

When calling the library

import bisect
bisect.bisect_left(arr, target)

Example of calling a library

arr = [1, 2, 3, 4, 5, 5, 5, 7, 8, 9, 9, 10]

#Where to insert target in an array, in order
target = 6
result = bisect.bisect_left(arr, target)
print("bisect_left:target not exists")
print(result)

#If targets already exist in the array, the leftmost location of the existing targets
target = 5
result = bisect.bisect_left(arr, target)
print("bisect_left:target exists")
print(result)

output:
bisect_left:target not exists
7
bisect_left:target exists
4

*** Implementation from 0 Example using bisect_left ***

from typing import List
def bisect_left(arr: List[int], target: int, left: int, right: int):
    while left < right:
        mid = (left + right) // 2
        if arr[mid] >= target: #Only here is different, please examine
            right = mid
        else:
            left = mid + 1

    return left #At this time, left and right are in the same place, so it doesn't matter which one you return.

*** Example of using implementation of bisect.bisect_left from 0 ***

#Where to insert target in an array, in order
target = 6
result = bisect_left(arr, target, 0, len(arr) - 1)
print("bisect_left:target not exists")
print(result)

#target If it already exists, the leftmost location of the existing targets
target = 5
result = bisect_left(arr, target, 0, len(arr) - 1)
print("bisect_left:target exists")
print(result)

output
bisect_left:target not exists
7
bisect_left:target exists
4

bisect.bisect_right

When calling the library

import bisect
bisect.bisect_right(arr, target)

Example of calling a library

import bisect


arr = [1, 2, 3, 4, 5, 5, 5, 7, 8, 9, 9, 10]

#Where to insert the target in the array, keeping the order
target = 3
result = bisect.bisect_right(arr, target)
print("bisect_left:target not exists")
print(result)

#target If it already exists, the rightmost location of the existing targets
target = 5
result = bisect.bisect_right(arr, target)
print("bisect_left:target exists")
print(result)

bisect_left:target not exists
3
bisect_left:target exists
7

*** Implementation of bisect.bisect_right from 0 ***

from typing import List
def bisect_right(arr:List[int],target:int,left:int,right:int)->int:
    while left < right:
        mid = (left + right) // 2

        if arr[mid] > target: #Only here is different, please examine
            right = mid
        else:
            left = mid + 1

    return left #At this time, left and right are in the same place, so it doesn't matter which one you return.

*** Example using bisect_right implemented from 0 ***

arr = [1, 2, 3, 4, 5, 5, 5, 7, 8, 9, 9, 10]

#Where to insert the target in the array, keeping the order
target = 3
result = bisect_right(arr, target,0, len(arr) - 1)
print("bisect_left:target not exists")
print(result)

#target If it already exists, the rightmost location of the existing targets
target = 5
result = bisect_right(arr, target, 0, len(arr) - 1)
print("bisect_left:target exists")
print(result)

output
bisect_left:target not exists
3
bisect_left:target exists
7

Find value

You can use the bisect_left and bisect_right index functions that should be inserted above to find the value. I have summarized three methods. If you have one value to look for, you can use either one. If there are multiple values ​​to look for, *** use the leftmost value ***, *** use the rightmost value ***, *** use the middle value *** , I summarized it for each goal.

Priority is given to the leftmost value

*** Find target, return index of target, return leftmost index if there are multiple targets, return -1 if not ***

def findXLeft(arr: List[int], target: int) -> int:
    res = bisect_left(arr, target, 0, len(arr) - 1) 
    if arr[res] == target:
        return res
    return -1

Priority is given to the middle value

*** Find target, return index of target, return index of middle target if there are multiple, return -1 if not ***

def findXCenter(arr: List[int],target: int) -> int:
    n = len(arr)
    left = 0
    right = n - 1

    while left < right:
        mid = (left + right) // 2
        if arr[mid] == target: #As soon as you find the middle value, return
            return mid

        if arr[mid] >= target: #here>When>=, Either one is ok
            right = mid
        else:
            left = mid + 1

    if arr[left] == target:
        return left

    return -1

Priority is given to the rightmost value

*** Find target, return index of target, return rightmost index if there are multiple targets, return -1 if not ***

def findXRight(arr: List[int], target: int) -> int:
    n = len(arr)
    right = n - 1
    
    res = bisect_right(arr, target, 0, len(arr) - 1)
    
    #When there is only one target
    if arr[res] == target:
        return right
    #If there are multiple targets, right and left will be the index next to the index of the rightmost target.
    if arr[max(0,res - 1)] == target:
        return res - 1
    return -1

Summary

It's confusing at first, but it's really interesting if you can understand how bisect works.