アルゴリズムとデータ構造 --- 理論編 --- 山本 真基

Presentation on theme: "アルゴリズムとデータ構造 --- 理論編 --- 山本 真基"— Presentation transcript:

1 アルゴリズムとデータ構造 --- 理論編 --- 山本 真基
二分探索 アルゴリズムとデータ構造 理論編 --- 山本　真基

2 二分探索 --- アルゴリズムの説明 --- 入力：　1; 0, 2, 3, 5, 5, 7, 9

3 二分探索 --- アルゴリズムの説明 --- 整数の列 入力：　1; 0, 2, 3, 5, 5, 7, 9

4 二分探索 --- アルゴリズムの説明 --- この列に 1 があるか？ 入力：　1; 0, 2, 3, 5, 5, 7, 9

5 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

6 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

7 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

8 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

9 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

10 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

11 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

12 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

13 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

14 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

15 探索終了！ 2 3 5 7 9 二分探索 --- アルゴリズムの説明 --- s > t より，探索終了
入力：　1; 0, 2, 3, 5, 5, 7, 9 1 2 3 5 4 7 6 9 探索終了！