もう二度と迷わない！絶対にバグらない二分探索の実装法

この記事について

二分探索アルゴリズムの概念自体はかなり基本的なものですが、いざ実装するとなると「ここのif文やwhile文の条件には=を入れていいんだっけ？」「leftやrightを動かすときはmiddle+1だっけ？middleそのままだっけ？」などたくさんの迷いポイントがあります。
この記事では、考えられる二分探索アルゴリズム全ての実装についてユニットテストを実施して結果を載せ、そこから見えるアルゴリズムの詳しい挙動について考察します。
この記事を全て読んだときには、正しい実装はどうすればいいのかきっちり覚えるはずです。

前提条件

• アルゴリズムの実装はGo(ver1.14)で行います。
• 考察すっ飛ばして結果だけ知りたい方は本記事の末尾まで一気に飛ばしてください。

読者に要求する前提知識

• 二分探索アルゴリズムの概要がわかっていること。(本記事では解説しません)

ループ条件一覧

二分探索の実装でポイントになる箇所は大きく4箇所です。

func bisect(array []int, key int) {
	var left, right, middle int
	left = 0
	right = len(array)
	for left < right { // ループ継続条件
		middle = ((right - left) / 2) + left
		if key <= array[middle] { // 範囲右寄せ,左寄せ条件
			right = middle // 左寄せ手法
		} else {
			left = middle // 右寄せ手法
		}
	}
	return
}

それぞれのポイント箇所で考えられる実装の組みは、以下16種類です。

No.	ループ継続条件	範囲左寄せ条件	範囲右寄せ条件	左寄せ手法	右寄せ手法
1	left<right	key<=array[middle]	array[middle]<key	right = middle	left = middle
2					left = middle+1
3				right = middle-1	left = middle
4					left = middle+1
5		key<array[middle]	array[middle]<=key	right = middle	left = middle
6					left = middle+1
7				right = middle-1	left = middle
8					left = middle+1
9	left<=right	key<=array[middle]	array[middle]<key	right = middle	left = middle
10					left = middle+1
11				right = middle-1	left = middle
12					left = middle+1
13		key<array[middle]	array[middle]<=key	right = middle	left = middle
14					left = middle+1
15				right = middle-1	left = middle
16					left = middle+1

#使用するテストケース
array=[1, 2, 3, 4, 4, 4, 5, 7, 8]に対して、期待する解答は以下の通り。

name	key	bisect_leftの場合	bisect_rightの場合
TestOver_left	-1	0	0
TestStop_even	2	1	2
TestStop_odd	3	2	3
TestStop_block	4	3	6
TestOver_right	9	9	9
TestNot_exist	6	7	7

arrayにすでにkeyが存在している場合の挙動は、

• bisect_leftの場合は挿入箇所は既存のkeyよりも左側
• bisect_rightの場合は挿入箇所が既存のkeyよりも右側

参考：Python標準ライブラリ：順序維持のbisect

##1

func bisect(array []int, key int) {
	var left, right, middle int
	left = 0
	right = len(array)
	for left < right {
		middle = ((right - left) / 2) + left
		if key <= array[middle] {
			right = middle
		} else {
			left = middle
		}
	}
	return
}

array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=-1 →(left, middle,right) = (0,0,0)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=2 →(left, middle,right) = (0,0,1)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=3 →(left, middle,right) = (1,1,2)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=4 →(left, middle,right) = (2,2,3)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=9 →(left, middle,right) = (8,8,9)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=6 →(left, middle,right) = (6,6,7)で無限ループ

##2

func bisect(array []int, key int) {
	var left, right, middle int
	left = 0
	right = len(array)
	for left < right {
		middle = ((right - left) / 2) + left
		if key <= array[middle] {
			right = middle
		} else {
			left = middle + 1
		}
	}
	return
}

array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=-1 →(left, middle,right) = (0,0,0)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=2 →(left, middle,right) = (1,0,1)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=3 →(left, middle,right) = (2,1,2)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=4 →(left, middle,right) = (3,3,3)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=9 →(left, middle,right) = (9,8,9)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=6 →(left, middle,right) = (7,6,7)でstop

→left, rightの値がbisect_leftとなる

##3

func bisect(array []int, key int) {
	var left, right, middle int
	left = 0
	right = len(array)
	for left < right {
		middle = ((right - left) / 2) + left
		if key <= array[middle] {
			right = middle - 1
		} else {
			left = middle
		}
	}
	return
}

array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=-1 →(left, middle,right) = (0,1,0)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=2 →(left, middle,right) = (0,1,0)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=3 →(left, middle,right) = (1,2,1)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=4 →(left, middle,right) = (2,2,3)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=9 →(left, middle,right) = (8,8,9)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=6 →(left, middle,right) = (6,7,6)でstop

##4

func bisect(array []int, key int) {
	var left, right, middle int
	left = 0
	right = len(array)
	for left < right {
		middle = ((right - left) / 2) + left
		if key <= array[middle] {
			right = middle - 1
		} else {
			left = middle + 1
		}
	}
	return
}

array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=-1 →(left, middle,right) = (0,1,0)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=2 →(left, middle,right) = (0,1,0)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=3 →(left, middle,right) = (2,2,1)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=4 →(left, middle,right) = (3,2,3)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=9 →(left, middle,right) = (9,8,9)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=6 →(left, middle,right) = (6,5,6)でstop

##5

func bisect(array []int, key int) {
	var left, right, middle int
	left = 0
	right = len(array)
	for left < right {
		middle = ((right - left) / 2) + left
		if key < array[middle] {
			right = middle
		} else {
			left = middle
		}
	}
	return
}

array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=-1 →(left, middle,right) = (0,0,0)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=2 →(left, middle,right) = (1,1,2)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=3 →(left, middle,right) = (2,2,3)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=4 →(left, middle,right) = (5,5,6)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=9 →(left, middle,right) = (8,8,9)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=6 →(left, middle,right) = (6,6,7)で無限ループ

##6

func bisect(array []int, key int) {
	var left, right, middle int
	left = 0
	right = len(array)
	for left < right {
		middle = ((right - left) / 2) + left
		if key < array[middle] {
			right = middle
		} else {
			left = middle + 1
		}
	}
	return
}

array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=-1 →(left, middle,right) = (0,0,0)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=2 →(left, middle,right) = (2,1,2)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=3 →(left, middle,right) = (3,3,3)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=4 →(left, middle,right) = (6,5,6)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=9 →(left, middle,right) = (9,8,9)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=6 →(left, middle,right) = (7,6,7)でstop

→left,rightの値がbisect_rightになる

##7

func bisect(array []int, key int) {
	var left, right, middle int
	left = 0
	right = len(array)
	for left < right {
		middle = ((right - left) / 2) + left
		if key < array[middle] {
			right = middle - 1
		} else {
			left = middle
		}
	}
	return
}

array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=-1 →(left, middle,right) = (0,1,0)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=2 →(left, middle,right) = (1,2,1)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=3 →(left, middle,right) = (2,2,3)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=4 →(left, middle,right) = (4,4,5)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=9 →(left, middle,right) = (8,8,9)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=6 →(left, middle,right) = (6,7,6)でstop

##8

func bisect(array []int, key int) {
	var left, right, middle int
	left = 0
	right = len(array)
	for left < right {
		middle = ((right - left) / 2) + left
		if key < array[middle] {
			right = middle - 1
		} else {
			left = middle + 1
		}
	}
	return
}

array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=-1 →(left, middle,right) = (0,1,0)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=2 →(left, middle,right) = (2,2,1)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=3 →(left, middle,right) = (3,2,3)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=4 →(left, middle,right) = (6,5,6)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=9 →(left, middle,right) = (9,8,9)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=6 →(left, middle,right) = (6,5,6)でstop

##9

func bisect(array []int, key int) {
	var left, right, middle int
	left = 0
	right = len(array)
	for left <= right {
		middle = ((right - left) / 2) + left
		if key <= array[middle] {
			right = middle
		} else {
			left = middle
		}
	}
	return
}

array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=-1 →(left, middle,right) = (0,0,0)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=2 →(left, middle,right) = (0,0,1)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=3 →(left, middle,right) = (1,1,2)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=4 →(left, middle,right) = (2,2,3)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=9 →(left, middle,right) = (8,8,9)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=6 →(left, middle,right) = (6,6,7)で無限ループ

##10

func bisect(array []int, key int) {
	var left, right, middle int
	left = 0
	right = len(array)
	for left <= right {
		middle = ((right - left) / 2) + left
		if key <= array[middle] {
			right = middle
		} else {
			left = middle + 1
		}
	}
	return
}

array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=-1 →(left, middle,right) = (0,0,0)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=2 →(left, middle,right) = (1,1,1)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=3 →(left, middle,right) = (2,2,2)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=4 →(left, middle,right) = (3,3,3)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=9 →(left, middle,right) = (9,9,9)でランタイムパニック
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=6 →(left, middle,right) = (7,7,7)で無限ループ

##11

func bisect(array []int, key int) {
	var left, right, middle int
	left = 0
	right = len(array)
	for left <= right {
		middle = ((right - left) / 2) + left
		if key <= array[middle] {
			right = middle - 1
		} else {
			left = middle
		}
	}
	return
}

array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=-1 →(left, middle,right) = (0,0,-1)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=2 →(left, middle,right) = (0,0,0)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=3 →(left, middle,right) = (1,1,1)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=4 →(left, middle,right) = (2,2,3)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=9 →(left, middle,right) = (8,8,9)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=6 →(left, middle,right) = (6,6,6)で無限ループ

##12

func bisect(array []int, key int) {
	var left, right, middle int
	left = 0
	right = len(array)
	for left <= right {
		middle = ((right - left) / 2) + left
		if key <= array[middle] {
			right = middle - 1
		} else {
			left = middle + 1
		}
	}
	return
}

array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=-1 →(left, middle,right) = (0,0,-1)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=2 →(left, middle,right) = (1,0,0)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=3 →(left, middle,right) = (2,2,1)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=4 →(left, middle,right) = (3,3,2)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=9 →(left, middle,right) = (9,9,9)でランタイムパニック
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=6 →(left, middle,right) = (7,6,6)でstop

##13

func bisect(array []int, key int) {
	var left, right, middle int
	left = 0
	right = len(array)
	for left <= right {
		middle = ((right - left) / 2) + left
		if key < array[middle] {
			right = middle
		} else {
			left = middle
		}
	}
	return
}

array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=-1 →(left, middle,right) = (0,0,0)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=2 →(left, middle,right) = (1,1,2)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=3 →(left, middle,right) = (2,2,3)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=4 →(left, middle,right) = (5,5,6)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=9 →(left, middle,right) = (8,8,9)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=6 →(left, middle,right) = (6,6,7)で無限ループ

##14

func bisect(array []int, key int) {
	var left, right, middle int
	left = 0
	right = len(array)
	for left <= right {
		middle = ((right - left) / 2) + left
		if key < array[middle] {
			right = middle
		} else {
			left = middle + 1
		}
	}
	return
}

array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=-1 →(left, middle,right) = (0,0,0)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=2 →(left, middle,right) = (2,2,2)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=3 →(left, middle,right) = (3,3,3)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=4 →(left, middle,right) = (6,6,6)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=9 →(left, middle,right) = (9,9,9)でランタイムパニック
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=6 →(left, middle,right) = (7,7,7)で無限ループ

##15

func bisect(array []int, key int) {
	var left, right, middle int
	left = 0
	right = len(array)
	for left <= right {
		middle = ((right - left) / 2) + left
		if key < array[middle] {
			right = middle - 1
		} else {
			left = middle
		}
	}
	return
}

array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=-1 →(left, middle,right) = (0,0,-1)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=2 →(left, middle,right) = (1,1,1)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=3 →(left, middle,right) = (2,2,3)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=4 →(left, middle,right) = (4,4,5)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=9 →(left, middle,right) = (8,8,9)で無限ループ
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=6 →(left, middle,right) = (6,6,6)で無限ループ

##16

func bisect(array []int, key int) {
	var left, right, middle int
	left = 0
	right = len(array)
	for left <= right {
		middle = ((right - left) / 2) + left
		if key < array[middle] {
			right = middle - 1
		} else {
			left = middle + 1
		}
	}
	return
}

array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=-1 →(left, middle,right) = (0,0,-1)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=2 →(left, middle,right) = (2,2,1)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=3 →(left, middle,right) = (3,3,2)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=4 →(left, middle,right) = (6,6,5)でstop
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=9 →(left, middle,right) = (9,9,9)でランタイムパニック
array=[1, 2, 3, 4, 4, 4, 5, 7, 8], key=6 →(left, middle,right) = (7,6,6)でstop

結果一覧

No.	ループ継続条件	範囲左寄せ条件	範囲右寄せ条件	左寄せ手法	右寄せ手法	ランタイムパニック	テストをpass
1	left<right	key<=array[middle]	array[middle]<key	right = middle	left = middle
2					left = middle+1		◯
3				right = middle-1	left = middle
4					left = middle+1		◯
5		key<array[middle]	array[middle]<=key	right = middle	left = middle
6					left = middle+1		◯
7				right = middle-1	left = middle
8					left = middle+1		◯
9	left<=right	key<=array[middle]	array[middle]<key	right = middle	left = middle
10					left = middle+1	◯
11				right = middle-1	left = middle
12					left = middle+1	◯
13		key<array[middle]	array[middle]<=key	right = middle	left = middle
14					left = middle+1	◯
15				right = middle-1	left = middle
16					left = middle+1	◯

#考察
以下、それぞれの実装においての挙動を考察します。

##状態遷移表
範囲右寄せ・左寄せ判定前の(left,middle,right)で状態番号を振る。
表中の色文字の意味は以下の通り。

• 青文字 : 全てのループ継続条件で停止
• 緑文字 : ループ継続条件left<rightなら停止
• 紫文字 : 無限ループ
• 赤文字 : 続行

状態番号	(left, middle,right)	right = middle	right = middle-1	left = middle	left = middle+1	備考
0	(n,n,n)	(n,n,n)→0	(n,n,n-1)→停止	(n,n,n)→0	(n+1,n,n)→停止
1	(n,n,n+1)	(n,n,n)→0	(n,n,n-1)→停止	(n,n,n+1)→1	(n+1,n,n+1)→0
2	(n,n+1,n+2)	(n,n+1,n+1)→1	(n,n+1,n)→0	(n+1,n+1,n+2)→1	(n+2,n+1,n+2)→0
3	(n,n+1,n+3)	(n,n+1,n+1)→1	(n,n+1,n)→0	(n+1,n+1,n+3)→2	(n+2,n+1,n+3)→1
4	(n,n+2,n+4)	(n,n+2,n+2)→2	(n,n+2,n+1)→1	(n+2,n+2,n+4)→2	(n+3,n+2,n+4)→1
…
2k	(n,n+k,n+2k)	(n,n+k,n+k)→k	(n,n+k,n+k-1)→k-1	(n+k,n+k,n+2k)→k	(n+k+1,n+k,n+2k)→k-1	k>=2
2k+1	(n,n+k,n+2k+1)	(n,n+k,n+k)→k	(n,n+k,n+k-1)→k-1	(n+k,n+k,n+2k+1)→k+1	(n+k+1,n+k,n+2k+1)→k	k>=2

無限ループが起こる条件

無限ループが起こっているパターンとしては2種類。

1. (n,n,n+1)

そのため(n,?,n+1)という状況になったときに、

• middle = ((right - left) / 2) + leftの部分でmiddle=left=nのまま変化しない
• left=middleの範囲右寄せが選ばれたときにleft=nで変化しない

のまま膠着状態になる。
→範囲右寄せ手法がleft=middleとなっている1,3,5,7,9,11,13,15で発生しうる。

(n,_,n+1)の状態はどうあがいても起きうるので、「middle = ((right - left) / 2) + leftの部分でmiddle=left=nのまま変化しない」を避けることは不可能。
そのため、left=middle+1は無限ループを起こさないための必要条件となる。

2. (n,n,n)

これで無限ループになるにはループ継続条件がleft<=rightでないといけない。このときに

• middle = ((right - left) / 2) + leftの部分でmiddle=leftのまま変化しない
• left=middleorright=middleが選ばれた場合、leftやrightが変化しない

という状態のまま膠着状態になる。
→範囲右寄せ・左寄せで必ずleft,rightの値が変化する12,16以外、つまり9,10,11,13,14,15で起こりうる。

stopする時の(left, middle,right)の組パターン

パターンとしては5種類。

1. (n,n,n)

whileループ開始時に(n,?,n+1)であった場合、次のmiddle定義で必ず(n,n,n+1)になる。
このとき、範囲左寄せが選ばれright=middleが実行された場合、(n,n,n)の状態になる。
このとき、left=rightで停止するループ継続条件left<rightであった場合、停止する。
→おきうるのは1,2,5,6

2.(n,n-1,n)

whileループ開始時に(n-1,?,n)であった場合、次のmiddle定義で必ず(n-1,n-1,n)になる。
このとき、範囲右寄せが選ばれleft=middle+1が実行された場合、(n,n-1,n)の状態になる。
このとき、left=rightで停止するループ継続条件left<rightであった場合、停止する。
→おきうるのは2,4,6,8

whileループ開始時に(n-2,?,n)であった場合、次のmiddle定義で必ず(n-2,n-1,n)になる。
このとき、範囲右寄せが選ばれleft=middle+1が実行された場合、(n,n-1,n)の状態になる。
このとき、left=rightで停止するループ継続条件left<rightであった場合、停止する。
→おきうるのは2,4,6,8

3.(n,n+1,n)

whileループ開始時に(n,?,n+3)であった場合、次のmiddle定義で必ず(n,n+1,n+3)になる。
このとき、範囲左寄せが選ばれright=middle-1が実行された場合、(n,n+1,n)の状態になる。
このとき、left=rightで停止するループ継続条件left<rightであった場合、停止する。
→おきうるのは3,4,7,8

whileループ開始時に(n,?,n+2)であった場合、次のmiddle定義で必ず(n,n+1,n+2)になる。
このとき、範囲左寄せが選ばれright=middle-1が実行された場合、(n,n+1,n)の状態になる。
このとき、left=rightで停止するループ継続条件left<rightであった場合、停止する。
→おきうるのは3,4,7,8

4.(n,n,n-1)

whileループ開始時に(n,?,n+1)であった場合、次のmiddle定義で必ず(n,n,n+1)になる。
このとき、範囲左寄せが選ばれright=middle-1が実行された場合、(n,n,n-1)の状態になる。
どんなループ継続条件であってもこれで停止する。
→おきうるのは3,4,7,8

whileループ開始時に(n,?,n)であった場合、次のmiddle定義で必ず(n,n,n)になる。
このとき、範囲左寄せが選ばれright=middle-1が実行された場合、(n,n,n-1)の状態になる。
どんなループ継続条件であってもこれで停止する。
→おきうるのは11,12,15,16

5.(n+1,n,n)

whileループ開始時に(n,?,n)であった場合、次のmiddle定義で必ず(n,n,n)になる。
このとき、範囲右寄せが選ばれleft=middle+1が実行された場合、(n+1,n,n)の状態になる。
どんなループ継続条件であってもこれで停止する。
→おきうるのは10,12,14,16

(n,n,n+1)がstopパターンにならずに無限ループパターンになるのに、(n,n,n)が両方あることの違い

whileループ終わりで(n,n,n+1)となった場合は、while条件がleft<rightでもleft<=rightでも次のループが問題なく回る。
対して(n,n,n)の場合はwhile条件がleft<rightのとき停止する。

ランタイムパニックが起こる条件

ランタイムパニックになるのがleft=right=len(a)のときのみ
このとき、次のループのmiddle = ((right - left) / 2) + leftの部分でleft=middle=right=len(a)という状況になる。
arrayの配列のインデックス範囲は0~len(a)-1なのでこれでエラーになる。

これが起こりうるのは10,12,14,16
<理由>

• ループ継続条件がleft<rightのときは、left=right=len(a)の時点で停止するのでmiddle=len(a)の代入が行われない
• 状態遷移図で「→0」となっているもののうち、範囲右寄せ・左寄せでrightが減少していないのがleft=middle+1のとき

ループ継続条件に=が入るとテストが一個も通らないわけ

少なくともテストを通すためには、無限ループとランタイムパニックを避ける必要がある。

• (n,n,n+1)の無限ループの条件に当たる→9,11,13,15
• (n,n,n)の無限ループの条件に当たる→9,10,11,13,14,15
• ランタイムパニックが起こる条件に当たる→10,12,14,16

→left<=rightである9~16は結局全部ダメなので、正しく実装するための必要条件はループ継続条件left<right

bisect_rightでもleftでもない4と8って？

whileループの間で常に成り立つ不変条件は以下の通り。

• 2のとき : i<left → array[i]<keyかつi>=right → key<=array[i]
• 4のとき : i<left → array[i]<keyかつi>right → key<=array[i]
• 6のとき : i<left → array[i]<=keyかつi>=right → key<array[i]
• 8のとき : i<left → array[i]<=keyかつi>right → key<array[I]

これにループが停止したときのleft,rightを代入すると以下のようになる。

(left,right)	(n,n)	(n,n-1)
2のときに代入	i<n → array[i]<keyかつi>=n → key<=array[i]	×
4のときに代入	keyとarray[n]の大小関係が決定されない	i<n → array[i]<keyかつi>n-1 → key<=array[i]
6のときに代入	i<n → array[i]<=keyかつi>=n → key<array[i]	×
8のときに代入	keyとarray[n]の大小関係が決定されない	i<n → array[i]<=keyかつi>n-1 → key<array[i]
4,8では大小関係がわからないときがあるので、このときのleftとrightに特別な意味はない。

bisectの返り値にleftを返すべきかmiddleを返すべきかrightを返すべきか

whileループの不変条件で出てくる変数はleftとrightであるので、middleはbisect関数の返り値に選ぶべきではない。
正しいbisect関数になりうる2,6では、停止時に常にleft=rightが成り立つため、leftとrightはどちらを返り値にしてもよい。

bisect_leftとbisect_rightはどう決まるのか

2と6の実装と不変条件をみると、

• 2のとき : array[middle]<keyとleft = middle+1からi<left → array[i]<keyが導かれる
• 6のとき : key<array[middle]とright = middleからi>=right → key<array[i]が導かれる

なので、array[middle]<keyのとき(=2)がbisect_leftとなり、key<array[middle]のとき(=6)の時がbisect_rightとなる。

まとめ

二分探索の正しい実装条件は以下の通りです。

bisect_left,right共通事項

• ループ継続条件はleft<right
  
  (Link→ループ継続条件に=が入るとテストが一個も通らないわけ)
• 左寄せ手法はright = middle
  
  (Link→bisect_rightでもleftでもない4と8って？)
• 右寄せ手法はleft = middle+1
  
  (Link→無限ループが起こる条件)

bisect_leftとrightの区別は

• leftだと範囲左寄せがkey<=array[middle]、範囲右寄せがarray[middle]<key
• rightだと範囲左寄せがkey<array[middle]、範囲右寄せがarray[middle]<=key

(Link→bisect_leftとbisect_rightはどう決まるのか)