二分查找解決數組元素定位問題

二分查找（Binary Search）

<a href="http://www.cnblogs.com/gaochundong/p/binary_search.html#binary_search_explanation">給定包含 n 個元素的已排序數組 sorted_array[]，求給定元素 x 的位置。</a>

<a href="http://www.cnblogs.com/gaochundong/p/binary_search.html#binary_search_recursive">遞歸方式（Recursive）實作</a>

<a href="http://www.cnblogs.com/gaochundong/p/binary_search.html#binary_search_iterative">疊代方式（Iterative）實作</a>

<a href="http://www.cnblogs.com/gaochundong/p/binary_search.html#binary_search_get_floor_value">給定包含 n 個元素的已排序數組 sorted_array[]，求小于等于給定元素 x 的最近位置（Floor Value）。</a>

<a href="http://www.cnblogs.com/gaochundong/p/binary_search.html#binary_search_find_ceiling_value">給定包含 n 個元素的已排序數組 sorted_array[]，求大于等于給定元素 x 的最近位置（Ceiling Value）。</a>

<a href="http://www.cnblogs.com/gaochundong/p/binary_search.html#binary_search_count_occurrences">給定包含 n 個元素的已排序數組 sorted_array[]，其中可能包含若幹重複的元素，求給定元素 x 重複的次數。</a>

<a href="http://www.cnblogs.com/gaochundong/p/binary_search.html#binary_search_index_of_minimum_rotated_array">給定包含 n 個元素的已排序數組 sorted_array[]，但數組被從中間某未知點翻轉為 A[]，求 A[] 數組中的最小元素。</a>

<a href="http://www.cnblogs.com/gaochundong/p/binary_search.html#binary_search_find_fixed_point">給定包含 n 個元素的已排序數組 sorted_array[]，查找其中元素位置等于元素值的位置（Fixed Point）。</a>

<a href="http://www.cnblogs.com/gaochundong/p/binary_search.html#binary_search_find_peak_value">給定包含 n 個元素的數組 array[]，查找某高點的值大于左右兩側的值的位置（Peak Position）。</a>

給定包含 n 個元素的已排序數組 sorted_array[]，求給定元素 x 的位置。

最簡單直接的辦法就是線性查找（Linear Search），從數組的最左端開始，逐個值與 x 進行比較，如果比對則傳回元素位置，如果不比對則右移一位繼續比較，如果比較到末尾仍為找到則傳回 -1。由此可知，線性查找的時間複雜度為 O(n)。

<a></a>

二分查找（Binary Search）算法使用了分治法（Divide and Conquer）來不斷縮小查找範圍，并充分利用已知的資訊将查找時間複雜度降低到 O(logn)。

那已知資訊就是：數組是已排序的。

這樣通過如下步驟可以減少比較次數：

将 x 與數組的中間的值進行比較；

如果 x 與中間的值相等，則直接傳回中間值的位置；

如果 x 較小，則若存在必出現在中間值的左側；

如果 x 較大，則若存在必出現在中間值的右側；

可以通過遞歸（Recursive）和疊代（Iterative）兩種方式來實作。

從上面的代碼可知，在最壞情況下需要 logn + 1 次比較操作。每個疊代周期内進行了 2 次比較，除非成功比對了元素。現在我們來嘗試盡量減少比較操作的數量，在 while 循環内僅進行一次比較。

現在我們通過使用二分查找（Binary Search）來解決一些常見問題。

給定包含 n 個元素的已排序數組 sorted_array[]，求小于等于給定元素 x 的最近位置（Floor Value）。

例如：sorted_array[] = [2, 3, 4, 6, 7, 8, 10, 12]，x = 9，則 FloorValue = 8。

這裡需要考慮幾個邊界條件：

如果數組内的所有元素都小于 x，則最後一個元素即為 FloorValue。

如果數組内的所有元素都大于 x，則實際上不存在 FloorValue，屬于異常情況，傳回 -1。

給定包含 n 個元素的已排序數組 sorted_array[]，求大于等于給定元素 x 的最近位置（Ceiling Value）。

例如：sorted_array[] = [2, 3, 4, 6, 7, 8, 10, 12]，x = 9，則 CeilingValue = 10。

如果數組内的所有元素都大于 x，則第一個元素即為 CeilingValue。

如果數組内的所有元素都小于 x，則實際上不存在 CeilingValue，屬于異常情況，傳回 -1。

給定包含 n 個元素的已排序數組 sorted_array[]，其中可能包含若幹重複的元素，求給定元素 x 重複的次數。

由于是已排序數組，則相同的元素肯定是連續的。這樣可以通過查找 x 的最左側出現和 x 的最右側出現，則中間的部分都是 x，出現次數 = right - left + 1。

例如：例如：sorted_array[] = [-1, 2, 3, 8, 8, 8, 8, 10]，x = 8，則重複的位置為 [8, 8, 8, 8]，則重複次數為 6 - 3 + 1 = 4 次。

給定包含 n 個元素的已排序數組 sorted_array[]，但數組被從中間某未知點翻轉為 A[]，求 A[] 數組中的最小元素。

實際上數組中的最小元素 x 将數組分成了左右兩側，左側的大于 x，右側的也大于 x。

給定包含 n 個元素的已排序數組 sorted_array[]，查找其中元素位置等于元素值的位置（Fixed Point）。

例如：sorted_array[] = { -10, -1, 0, 3, 10, 11, 30, 50 }，則 Fixed Point = 3。

給定包含 n 個元素的數組 array[]，查找某高點的值大于左右兩側的值的位置（Peak Position）。

例如：array[] = { 1, 3, 20, 4, 1 }，則 Peak Value = 20，Peak Position = 2。

<a>本文轉自匠心十年部落格園部落格，原文連結：http://www.cnblogs.com/gaochundong/p/binary_search.html，如需轉載請自行聯系原作者</a>