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

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

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

## 読者に要求する前提知識
- 二分探索アルゴリズムの概要がわかっていること。(本記事では解説しません)

# ループ条件一覧
二分探索の実装でポイントになる箇所は大きく4箇所です。

```golang
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](https://qiita.com/ta7uw/items/d6d8f0ddb215c3677cd3)

##1
```golang
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
```golang
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
```golang
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
```golang
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
```golang
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
```golang
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
```golang
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
```golang
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
```golang
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
```golang
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
```golang
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
```golang
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
```golang
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
```golang
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
```golang
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
```golang
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)で状態番号を振る。
表中の色文字の意味は以下の通り。

- <font color="blue">青文字</font> : 全てのループ継続条件で停止
- <font color="green">緑文字</font> : ループ継続条件`left<right`なら停止
- <font color="purple">紫文字</font> : 無限ループ
- <font color="red">赤文字</font> : 続行

|状態番号|(left, middle,right)|right = middle|right = middle-1|left = middle|left = middle+1|備考|
|---|---|---|---|---|---|---|
|0|(n,n,n)|(n,n,n)→<font color="purple">0</font>|(n,n,n-1)→<font color="blue">停止</font>|(n,n,n)→<font color="purple">0</font>|(n+1,n,n)→<font color="blue">停止</font>||
|1|(n,n,n+1)|(n,n,n)→<font color="green">0</font>|(n,n,n-1)→<font color="blue">停止</font>|(n,n,n+1)→<font color="purple">1</font>|(n+1,n,n+1)→<font color="green">0</font>||
|2|(n,n+1,n+2)|(n,n+1,n+1)→<font color="red">1</font>|(n,n+1,n)→<font color="green">0</font>|(n+1,n+1,n+2)→<font color="red">1</font>|(n+2,n+1,n+2)→<font color="green">0</font>||
|3|(n,n+1,n+3)|(n,n+1,n+1)→<font color="red">1</font>|(n,n+1,n)→<font color="green">0</font>|(n+1,n+1,n+3)→<font color="red">2</font>|(n+2,n+1,n+3)→<font color="red">1</font>||
|4|(n,n+2,n+4)|(n,n+2,n+2)→<font color="red">2</font>|(n,n+2,n+1)→<font color="red">1</font>|(n+2,n+2,n+4)→<font color="red">2</font>|(n+3,n+2,n+4)→<font color="red">1</font>||
|…||||||
|2k|(n,n+k,n+2k)|(n,n+k,n+k)→<font color="red">k</font>|(n,n+k,n+k-1)→<font color="red">k-1</font>|(n+k,n+k,n+2k)→<font color="red">k</font>|(n+k+1,n+k,n+2k)→<font color="red">k-1</font>|k>=2|
|2k+1|(n,n+k,n+2k+1)|(n,n+k,n+k)→<font color="red">k</font>|(n,n+k,n+k-1)→<font color="red">k-1</font>|(n+k,n+k,n+2k+1)→<font color="red">k+1</font>|(n+k+1,n+k,n+2k+1)→<font color="red">k</font>|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=middle`or`right=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)`の代入が行われない
- 状態遷移図で「→<font color="green">0</font>」となっているもののうち、範囲右寄せ・左寄せで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`<br>
(Link→[ループ継続条件に=が入るとテストが一個も通らないわけ](#ループ継続条件にが入るとテストが一個も通らないわけ))
- 左寄せ手法は`right = middle`<br>
(Link→[bisect_rightでもleftでもない4と8って？](#bisect_rightでもleftでもない4と8って))
- 右寄せ手法は`left = middle+1`<br>
(Link→[無限ループが起こる条件](#無限ループが起こる条件))

bisect_leftとrightの区別は

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

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