二分探索
STEP1
STEP2
プログラムの図的表現
key = 8
0
1
low
1
3
2
4
3
8
4
13
5
14
6
18
7
20
8
21
9
25
high
変数の動き
変数「mid」の動き
mid =
プログラム操作
int binary_search(int key) {
int low = 0 ;
int high = N - 1;
int mid;
while (low <= high) {
mid = (low + high) /2;
if (s[mid] == key ) {
return (mid);
}
if (s[mid] > key)
high = mid - 1;
else
low = mid + 1 ;
}
return -1;
}
プログラムの図的表現
key = 8
0
1
low
1
3
2
4
3
8
4
13
5
14
6
18
7
20
8
21
9
25
high