python 二分探索 bisect.bisect_leftとbisect.bisect_rightを0から実装するのは意外と簡単

###背景
pythonの二分探索は普段bisectライブラリを使って実装していますが、今回0から使ってみました。

bisect.bisect_left

ライブラリを呼び出す場合

import bisect
bisect.bisect_left(arr, target)

####ライブラリを呼び出す例

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

# 配列の中にtargetを入れようとして、順序を保つまま、挿入するべきな場所
target = 6
result = bisect.bisect_left(arr, target)
print("bisect_left:target not exists")
print(result)

# 配列にtargetすでにある場合、すでにあるtarget達の一番左側の場所
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

0からの実装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: #ここだけが違う、吟味してください
            right = mid
        else:
            left = mid + 1

    return left #この時にleftとrightは同じ場所だから、どっちをreturnしても大丈夫

bisect.bisect_leftを0からの実装を使用する例

# 配列の中にtargetを入れようとして、順序を保つまま、挿入するべきな場所
target = 6
result = bisect_left(arr, target, 0, len(arr) - 1)
print("bisect_left:target not exists")
print(result)

# targetすでにある場合は、すでにあるtarget達の一番左側の場所
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

ライブラリを呼び出す場合

import bisect
bisect.bisect_right(arr, target)

####ライブラリを呼び出す例

import bisect


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

# 配列の中にtargetを入れ用として、順序を保つまま、挿入するべき場所
target = 3
result = bisect.bisect_right(arr, target)
print("bisect_right:target not exists")
print(result)

# targetすでにある場合は、すでにあるtarget達の一番右の場所
target = 5
result = bisect.bisect_right(arr, target)
print("bisect_right:target exists")
print(result)

bisect_left:target not exists
3
bisect_left:target exists
7

bisect.bisect_rightを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: #ここだけが違う、吟味してください
            right = mid
        else:
            left = mid + 1

    return left #この時にleftとrightは同じ場所だから、どっちをreturnしても大丈夫

0からの実装したbisect_rightを使用した例

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

# 配列の中にtargetを入れ用として、順序を保つまま、挿入するべき場所
target = 3
result = bisect_right(arr, target,0, len(arr) - 1)
print("bisect_left:target not exists")
print(result)

# targetすでにある場合は、すでにあるtarget達の一番右の場所
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

###値を探す###

上記のbisect_leftとbisect_rightという挿入するべきなindex関数を活かして、値を探すことをできます。
三つの方法をまとめました。
探す値は一つがある場合、どっちでも使えます。
探す値は複数存在する場合、一番左側の値を使うか、一番右側の値をつかるか、真ん中の値を使うか、目標ごとにまとめました。

####一番左側の値を優先####
targetを探します、targetのindexを返す、複数targetあるなら、一番左側のindexを返す、ないなら-1を返す

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

####真ん中の値を優先####
targetを探します、targetのindexを返す,複数あるなら、真ん中のtargetのindexを返す、ないなら-1を返す

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: #真ん中の値を見つけたら、すぐreturn
            return mid

        if arr[mid] >= target: #ここで >　と　>=　、どっちでも大丈夫です
            right = mid
        else:
            left = mid + 1

    if arr[left] == target:
        return left

    return -1

####一番右側の値を優先####
targetを探します、targetのindexを返す、複数targetあるなら、一番右側のindexを返す、ないなら-1を返す

def findXRight(arr: List[int], target: int) -> int:
    n = len(arr)
    right = n - 1
    
    res = bisect_right(arr, target, 0, len(arr) - 1)
    
    #targetは一つの場合
    if arr[res] == target:
        return right
    #targetは複数ある場合、rightとleftは一番右のtargetのindexの次のindexになるため
    if arr[max(0,res - 1)] == target:
        return res - 1
    return -1

func findLeft(arr []int, target int) int {
	l := 0
	r := len(arr) - 1

	for l < r {
		x := float64((l + r) / 2.0)
		mid := int(math.Floor(x))

		if arr[mid] < target {
			l = mid + 1
			continue
		}
		r = mid
	}

	//if arr[l] <= target{
	//	return l
	//}

	//return max(0,l-1)
	return l
}

func findRight(arr []int, target int) int {
	l := 0
	r := len(arr) - 1
	for l < r {
		x := float64((l + r) / 2.0)
		mid := int(x)
		if arr[mid] <= target{
			l = mid + 1
			continue
		}
		r = mid
	}

	if arr[l] <= target {
		return l
	}

	return max(0,l - 1)
}

###まとめ

最初を考えるとややこしいですが、bisectの仕組みをよく理解できれば、すごく面白いです。