|
還有一個(gè)典型的遞歸例子是對(duì)已排序數(shù)組的二分查找算法。
現(xiàn)在有一個(gè)已經(jīng)排序好的數(shù)組，要在這個(gè)數(shù)組中查找一個(gè)元素，以確定它是否在這個(gè)數(shù)組中，很一般的想法是順序檢查每個(gè)元素，看它是否與待查找元素相同。這個(gè)方法很容易想到，但它的效率不能讓人滿意，它的復(fù)雜度是O(n)的。現(xiàn)在我們來(lái)看看遞歸在這里能不能更有效。
還是考慮上面的兩個(gè)條件：
- 第一：這個(gè)問(wèn)題是否可以分解為形式相同但規(guī)模更小的問(wèn)題？
- 第二：如果存在這樣一種分解，那么這種分解是否存在一種簡(jiǎn)單情境？
考慮條件一：我們可以這樣想，如果想把問(wèn)題的規(guī)模縮小，我們應(yīng)該做什么？
可以的做法是：我們先確定數(shù)組中的某些元素與待查元素不同，然后再在剩下的元素中查找，這樣就縮小了問(wèn)題的規(guī)模。那么如何確定數(shù)組中的某些元素與待查元素不同呢？ 考慮到我們的數(shù)組是已經(jīng)排序的，我們可以通過(guò)比較數(shù)組的中值元素和待查元素來(lái)確定待查元素是在數(shù)組的前半段還是后半段。這樣我們就得到了一種把問(wèn)題規(guī)?？s小的方法。
接著考慮條件二：簡(jiǎn)單情境是什么呢？
容易發(fā)現(xiàn)，如果中值元素和待查元素相等，就可以確定待查元素是否在數(shù)組中了，這是一種簡(jiǎn)單情境，那么它是不是唯一的簡(jiǎn)單情境呢？ 考慮元素始終不與中值元素相等，那么我們最終可能得到了一個(gè)無(wú)法再分的小規(guī)模的數(shù)組，它只有一個(gè)元素，那么我們就可以通過(guò)比較這個(gè)元素和待查元素來(lái)確定最后的結(jié)果。這也是一種簡(jiǎn)單情境。
好了，基于以上的分析，我們發(fā)現(xiàn)這個(gè)問(wèn)題可以用遞歸來(lái)解決，二分法的代碼如下：
04 | void selectionSort(int data[], int count); |
05 | int binary_search(int *a, int n, int key); |
13 | printf("排序前數(shù)組為："); |
21 | count = sizeof(arr)/sizeof(arr[0]); |
22 | selectionSort(arr, count); |
24 | printf("\n排序后數(shù)組為："); |
27 | printf("%d ", arr[i]); |
30 | printf("\n請(qǐng)輸入要查找的數(shù)字："); |
33 | rs = binary_search(arr, 10, key); |
37 | void selectionSort(int data[], int count) |
40 | for(i = 0; i < count; i ++) { |
43 | for(j = i + 1; j < count; j ++) |
44 | if(data[j] < data[min]) |
52 | int binary_search(int *data, int n, int key) |
56 | return (data[0] == key); |
59 | printf("mid=%d\n", data[mid]); |
60 | if(data[mid-1] == key) |
62 | else if(data[mid-1] > key) |
64 | printf("key %d 比 data[mid-1] %d 小，取前半段 \n", key, data[mid-1]); |
65 | return binary_search(&data[0], mid, key); |
69 | printf("key %d 比 data[mid-1] %d 大，取后半段 \n", key, data[mid-1]); |
70 | return binary_search(&data[mid], n - mid, key); |
程序運(yùn)行結(jié)果：
1 | 排序前數(shù)組為：53 27 26 99 20 17 15 25 23 63 |
2 | 排序后數(shù)組為：15 17 20 23 25 26 27 53 63 99 |
5 | key 20 比 data[mid-1] 25 小，取前半段 |
7 | key 20 比 data[mid-1] 17 大，取后半段 |
這個(gè)算法的復(fù)雜度是O(logn)的，顯然要優(yōu)于先前提到的樸素的順序查找法。
|
