二分查找

歸納

優點：比較次數少、查找速度快、平均性能好

缺點：待查找表為有序表、插入删除困難

時間複雜度：O(logN)

實用場景：有序數組

思路

假設表為升序排列，中間元素和待查元素比較，如果中間元素和待查元素相等找到了；如果小于則在前半段找；否則在後半段找。

遞歸

<a></a>

疊代

案例一

在有序數組1 2 3 3 3 3 4 5中3出現的次數為4，1出現的次數為1。

分析：有序數組查找——二分查找。二分找到被查找的元素，再兩邊擴充，直到找全為止。

參考代碼

案例二

求旋轉數組的最小元素（把一個數組最開始的若幹個元素搬到數組的末尾，稱之為數組的旋轉。輸入一個排好序的數組的一個旋轉，輸出旋轉數組的最小元素。例如數組{3, 4, 5, 1, 2}為{1, 2, 3, 4, 5}的一個旋轉，該數組的最小值為1）

思路：有序數組——二分查找。

中間位置是mid，把數組分成左右兩部分

左部分的最小值left = min(a[beg], a[min-1])

右部分的最小值right=min(a[mid+1], a[end])

如果a[mid]最小，則最小值為a[mid]

如果left最小，則最小值在beg~mid-1

如果right最小，則最小值在mid+1~end

測試

本文轉自jihite部落格園部落格，原文連結：http://www.cnblogs.com/kaituorensheng/p/3550151.html，如需轉載請自行聯系原作者