程式設計 基礎課程 APCS 關於我們 學生作品

2016觀念題③

✭✭✭✩✩

循序搜尋 二分搜尋

 1

 2

 3

 4

 5

 6

 7

 8

 9

10

11

12

int f1(int a[], int value) {

    int r_value = -1;

    int i = 0;

    while (i < 100) {

        if (a[i] == value) {

            r_value = i;

            break;

        }

        i = i + 1;

    }

    return r_value;

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

int f2(int a[], int value) {

    int r_value = -1;

    int low = 0, high = 99;

    int mid;

    while (low <= high) {

        mid = (low + high) / 2;

        if (a[mid] == value) {

            r_value = mid;

            break;

        } else if (a[mid] < value) {

            low = mid + 1;

        } else {

            high = mid - 1;

        }

    }

    return r_value;

}

給定一整數陣列 a[0]、 a[1]、 …、 a[99]且 a[k]=3k+1,以 value=100 呼叫以下兩函式,假設函式 f1 及 f2 之 while 迴圈主體分別執行 n1 與 n2 次 (i.e, 計算 if 敘述執行次數,不包含 else if 敘述),請問 n1 與 n2 之值為何? 註: (low + high)/2 只取整數部分。

(A) n1=33, n2=4

(B) n1=33, n2=5

(C) n1=34, n2=4

(D) n1=34, n2=5

解題說明:

這題在比較「循序搜尋」和「二分搜尋」,「3k+1」只是要快速創造出100個排序好的數字,沒有特殊的意義。左邊程式相對的簡單,只是一個一個比對是否正確而已。右邊的程式稍微複雜一點,原理就是控制索引的最小值「low」和最大值「high」來縮小範圍。

i從0開始,一直到 i=33,就會得到 a[i] = 100,從0~33一共是34次。

根據提示,「low」和「high」的變化表列如下,我們可以看到第5次就能得到 a[i] = 100

i

a[i]

0

1

1

4

2

7

...

...

33

100

low

high

mid

a[mid]

0

99

49

148

0

48

24

73

25

48

36

109

25

35

30

91

31

35

33

100

一樣是要找到「100」這個值,用「循序搜尋」要34次,用「二分搜尋」只要5次。如果要找的量增加,這個差距還會更大。但是「循序搜尋」還是有它的優點,就是資料不用排序,程式碼也很簡單易懂,在資料量不大時還是相當有用的。

如果對上述「二分搜尋」的操作方式不清楚,可以參考我們整理出來的簡化範例和圖示如下:

附錄3a. 簡化範例1

給定10個數的陣列 a = [1,4,7,10,13,16,19,22,25,28] ,用二分搜尋找到「10」的演算過程如下:

a[ ]

0

1

2

3

4

5

6

7

8

9

a[mid]

1

4

7

10

13

16

19

22

25

28

1st

a[mid] = 13 大於「10」,所以新的 high = 4 -1 = 3

2nd

                                                                                                                             

a[mid] = 4 小於「10」,所以新的 low = 1 +1 = 2

3rd

⇡⬆

a[mid] = 7 小於「10」,所以新的 low = 2 +1 = 3

4th

⇡⇑

a[mid] = 3 得到正解


附錄3b. 簡化範例2

給定20個數的陣列 a = [1,4,7,10,13,16,19,22,25,28,...] ,用二分搜尋找到「10」的演算過程如下:

a[ ]

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

a[mid]

1

4

7

10

13

16

19

22

25

28

31

34

37

40

43

46

49

52

55

58

1st

a[mid] = 31 大於「10」,所以新的 high = 10 -1 = 9

2nd

a[mid] = 16 大於「10」,所以新的 high =  -1 = 4

3rd

a[mid] = 7 小於「10」,所以新的 low = 2 +1 = 3

4th

⇡⬆

a[mid] = 3 得到正解

附錄3c. 原始範例

給定100個數的陣列 a = [1,4,7,10,13,16,19,22,25,28,...] ,用二分搜尋找到「100」的演算過程如下:

a[ ]

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

...

99

a[mid]

1

4

7

10

13

16

19

22

25

28

31

34

37

40

43

46

49

52

55

58

61

64

67

70

73

76

79

82

85

88

91

94

97

100

103

106

109

112

115

118

121

124

127

130

133

136

139

142

145

148

...

298

1st

2nd

3rd

4th

5th