アルゴリズムとデータ構造 --- 理論編 --- 山本 真基 二分探索 アルゴリズムとデータ構造 --- 理論編 --- 山本 真基
二分探索 --- アルゴリズムの説明 --- 入力： 1; 0, 2, 3, 5, 5, 7, 9
二分探索 --- アルゴリズムの説明 --- 整数の列 入力： 1; 0, 2, 3, 5, 5, 7, 9
二分探索 --- アルゴリズムの説明 --- この列に 1 があるか？ 入力： 1; 0, 2, 3, 5, 5, 7, 9
2 3 5 5 7 9 二分探索 --- アルゴリズムの説明 --- 入力の整数の列と 配列の番号 入力： 1; 0, 2, 3, 5, 5, 7, 9 1 2 3 4 5 6 7 2 3 5 5 7 9
2 3 5 7 9 二分探索 --- アルゴリズムの説明 --- s=1, t=7 入力： 1; 0, 2, 3, 5, 5, 7, 9 1 入力： 1; 0, 2, 3, 5, 5, 7, 9 1 2 3 5 4 7 6 9
2 3 5 7 9 二分探索 --- アルゴリズムの説明 --- l l = (1+7)/2 = 4 入力： 1; 0, 2, 3, 5, 5, 7, 9 1 2 3 5 4 7 6 9 l
2 3 5 7 9 二分探索 --- アルゴリズムの説明 --- l 1 は 5 でない，かつ， 1 は 5 より小さいので 入力： 1; 0, 2, 3, 5, 5, 7, 9 1 2 3 5 4 7 6 9 l
2 3 5 7 9 二分探索 --- アルゴリズムの説明 --- s = 1, t = 3 入力： 1; 0, 2, 3, 5, 5, 7, 9 1 2 3 5 4 7 6 9
2 3 5 7 9 二分探索 --- アルゴリズムの説明 --- l l = (1+3)/2 = 2 入力： 1; 0, 2, 3, 5, 5, 7, 9 1 2 3 5 4 7 6 9 l
2 3 5 7 9 二分探索 --- アルゴリズムの説明 --- l 1 は 2 でない，かつ， 1 は 2 より小さいので 入力： 1; 0, 2, 3, 5, 5, 7, 9 1 2 3 5 4 7 6 9 l
2 3 5 7 9 二分探索 --- アルゴリズムの説明 --- l s = t = l = 1 入力： 1; 0, 2, 3, 5, 5, 7, 9 1 2 3 5 4 7 6 9 l
2 3 5 7 9 二分探索 --- アルゴリズムの説明 --- l 1 は 0 でない，かつ， 1 は 0 より大きいので 入力： 1; 0, 2, 3, 5, 5, 7, 9 1 2 3 5 4 7 6 9 l
2 3 5 7 9 二分探索 --- アルゴリズムの説明 --- s = 2 > t = 1 !!! 入力： 1; 0, 2, 3, 5, 5, 7, 9 1 2 3 5 4 7 6 9
探索終了！ 2 3 5 7 9 二分探索 --- アルゴリズムの説明 --- s > t より，探索終了 入力： 1; 0, 2, 3, 5, 5, 7, 9 1 2 3 5 4 7 6 9 探索終了！