一、什么是二分查找？

二分查找針對的是一個有序的數(shù)據(jù)集合，每次通過跟區(qū)間中間的元素對比，將待查找的區(qū)間縮小為之前的一半，直到找到要查找的元素，或者區(qū)間縮小為0。

二、時間復雜度分析？

1.時間復雜度
假設數(shù)據(jù)大小是n，每次查找后數(shù)據(jù)都會縮小為原來的一半，最壞的情況下，直到查找區(qū)間被縮小為空，才停止。所以，每次查找的數(shù)據(jù)大小是：n，n/2，n/4，…，n/(2^{k)，…，這是一個等比數(shù)列。當n/(2}k)=1時，k的值就是總共縮小的次數(shù)，也是查找的總次數(shù)。而每次縮小操作只涉及兩個數(shù)據(jù)的大小比較，所以，經(jīng)過k次區(qū)間縮小操作，時間復雜度就是O(k)。通過n/(2^k)=1，可求得k=log2n，所以時間復雜度是O(logn)。
2.認識O(logn)
①這是一種極其高效的時間復雜度，有時甚至比O(1)的算法還要高效。為什么？
②因為logn是一個非常“恐怖“的數(shù)量級，即便n非常大，對應的logn也很小。比如n等于2的32次方，也就是42億，而logn才32。
③由此可見，O(logn)有時就是比O(1000)，O(10000)快很多。

三、如何實現(xiàn)二分查找？

1.循環(huán)實現(xiàn)
代碼實現(xiàn)：

public int binarySearch1(int[] a, int val){ int start = 0; int end = a.length - 1; while(start <= end){ int mid = start + (end - start) / 2; if(a[mid] > val) end = mid - 1; else if(a[mid] < val) start = mid + 1; else return mid; } return -1; }

注意事項：
①循環(huán)退出條件是：start<=end，而不是start<end。
②mid的取值，使用mid=start + (end - start) / 2，而不用mid=(start + end)/2，因為如果start和end比較大的話，求和可能會發(fā)生int類型的值超出最大范圍。為了把性能優(yōu)化到極致，可以將除以2轉(zhuǎn)換成位運算，即start + ((end - start) >> 1)，因為相比除法運算來說，計算機處理位運算要快得多。
③start和end的更新：start = mid - 1，end = mid + 1，若直接寫成start = mid，end=mid，就可能會發(fā)生死循環(huán)。
2.遞歸實現(xiàn)

public int binarySearch(int[] a, int val){ return bSear(a, val, 0, a.length-1); } private int bSear(int[] a, int val, int start, int end) { if(start > end) return -1; int mid = start + (end - start) / 2; if(a[mid] == val) return mid; else if(a[mid] > val) end = mid - 1; else start = mid + 1; return bSear(a, val, start, end); }

四、使用條件（應用場景的局限性）

1.二分查找依賴的是順序表結(jié)構(gòu)，即數(shù)組。
2.二分查找針對的是有序數(shù)據(jù)，因此只能用在插入、刪除操作不頻繁，一次排序多次查找的場景中。
3.數(shù)據(jù)量太小不適合二分查找，與直接遍歷相比效率提升不明顯。但有一個例外，就是數(shù)據(jù)之間的比較操作非常費時，比如數(shù)組中存儲的都是長度超過300的字符串，那這是還是盡量減少比較操作使用二分查找吧。
4.數(shù)據(jù)量太大也不是適合用二分查找，因為數(shù)組需要連續(xù)的空間，若數(shù)據(jù)量太大，往往找不到存儲如此大規(guī)模數(shù)據(jù)的連續(xù)內(nèi)存空間。

五、四種常見的二分查找變形問題

1.查找第一個值等于給定值的元素

public int bsearch(int[] a, int n, int value) {int low = 0;int high = n - 1;while (low <= high) {int mid = low + ((high - low) >> 1);if (a[mid] > value) {high = mid - 1;} else if (a[mid] < value) {low = mid + 1;} else {if ((mid == 0) || (a[mid - 1] != value)) return mid;else high = mid - 1;}}return -1; }

2.查找最后一個值等于給定值的元素
如果 a[mid]這個元素已經(jīng)是數(shù)組中的最后一個元素了，那它肯定是我們要找的；如果 a[mid]的后一個元素 a[mid+1]不等于 value，那也說明 a[mid]就是我們要找的最后一個值等于給定值的元素。
如果我們經(jīng)過檢查之后，發(fā)現(xiàn) a[mid]后面的一個元素 a[mid+1]也等于 value，那說明當前的這個 a[mid]并不是最后一個值等于給定值的元素。我們就更新 low=mid+1，因為要找的元素肯定出現(xiàn)在[mid+1, high]之間。

public int bsearch(int[] a, int n, int value) {int low = 0;int high = n - 1;while (low <= high) {int mid = low + ((high - low) >> 1);if (a[mid] > value) {high = mid - 1;} else if (a[mid] < value) {low = mid + 1;} else {if ((mid == n - 1) || (a[mid + 1] != value)) return mid;else low = mid + 1;}}return -1; }

3.查找第一個大于等于給定值的元素
如果 a[mid]小于要查找的值 value，那要查找的值肯定在[mid+1, high]之間，所以，我們更新 low=mid+1。
對于 a[mid]大于等于給定值 value 的情況，我們要先看下這個 a[mid]是不是我們要找的第一個值大于等于給定值的元素。如果 a[mid]前面已經(jīng)沒有元素，或者前面一個元素小于要查找的值 value，那 a[mid]就是我們要找的元素。
如果 a[mid-1]也大于等于要查找的值 value，那說明要查找的元素在[low, mid-1]之間，所以，我們將 high 更新為 mid-1。

public int bsearch(int[] a, int n, int value) {int low = 0;int high = n - 1;while (low <= high) {int mid = low + ((high - low) >> 1);if (a[mid] >= value) {if ((mid == 0) || (a[mid - 1] < value)) return mid;else high = mid - 1;} else {//肯定low = mid + 1;}}return -1; }

4.查找最后一個小于等于給定值的元素

public int bsearch(int[] a, int n, int value) {int low = 0;int high = n - 1;while (low <= high) {int mid = low + ((high - low) >> 1);if (a[mid] >= value) {if ((mid == 0) || (a[mid - 1] < value)) return mid;else high = mid - 1;} else {low = mid + 1;}}return -1; }

六、適用性分析

1.凡事能用二分查找解決的，絕大部分我們更傾向于用散列表或者二叉查找樹，即便二分查找在內(nèi)存上更節(jié)省，但是畢竟內(nèi)存如此緊缺的情況并不多。
2.求“值等于給定值”的二分查找確實不怎么用到，二分查找更適合用在”近似“查找問題上。比如上面講幾種變體。

五、思考

1.如何在1000萬個整數(shù)中快速查找某個整數(shù)？
我們的內(nèi)存限制是 100MB，每個數(shù)據(jù)大小是 8 字節(jié)，最簡單的辦法就是將數(shù)據(jù)存儲在數(shù)組中，內(nèi)存占用差不多是 80MB，符合內(nèi)存的限制。我們可以先對這 1000 萬數(shù)據(jù)從小到大排序，然后再利用二分查找算法，就可以快速地查找想要的數(shù)據(jù)了。
①1000萬個整數(shù)占用存儲空間為40MB，占用空間不大，所以可
以全部加載到內(nèi)存中進行處理；
②用一個1000萬個元素的數(shù)組存儲，然后使用快排進行升序排序，時間復雜度為O(nlogn)
③在有序數(shù)組中使用二分查找算法進行查找，時間復雜度為O(logn)
2.如何編程實現(xiàn)“求一個數(shù)的平方根”？要求精確到小數(shù)點后6位？

public static double sqrt(double x, double precision) { if (x < 0) { return Double.NaN; } double low = 0; double up = x; if (x < 1 && x > 0) { /** 小于1的時候*/ low = x; up = 1; } double mid = low + (up - low)/2; while(up - low > precision) { if (mid * mid > x ) {//TODO mid可能會溢出 改成mid > x / mid up = mid; } else if (mid * mid < x) { low = mid; } else { return mid; } mid = low + (up - low)/2; } return mid; }

3.如何快速定位出一個IP地址的歸屬地？
[202.102.133.0, 202.102.133.255] 山東東營市
[202.102.135.0, 202.102.136.255] 山東煙臺
[202.102.156.34, 202.102.157.255] 山東青島
[202.102.48.0, 202.102.48.255] 江蘇宿遷
[202.102.49.15, 202.102.51.251] 江蘇泰州
[202.102.56.0, 202.102.56.255] 江蘇連云港
假設我們有 12 萬條這樣的 IP 區(qū)間與歸屬地的對應關(guān)系，如何快速定位出一個IP地址的歸屬地呢？
如果 IP 區(qū)間與歸屬地的對應關(guān)系不經(jīng)常更新，我們可以先預處理這 12 萬條數(shù)據(jù)，讓其按照起始 IP 從小到大排序。如何來排序呢？我們知道，IP 地址可以轉(zhuǎn)化為 32 位的整型數(shù)。所以，我們可以將起始地址，按照對應的整型值的大小關(guān)系，從小到大進行排序
。然后，這個問題就可以轉(zhuǎn)化為我剛講的第四種變形問題“在有序數(shù)組中，查找最后一個小于等于某個給定值的元素”了。
當我們要查詢某個 IP 歸屬地時，我們可以先通過二分查找，找到最后一個起始 IP 小于等于這個 IP 的 IP 區(qū)間，然后，檢查這個 IP 是否在這個 IP 區(qū)間內(nèi)，如果在，我們就取出對應的歸屬地顯示；如果不在，就返回未查找到。

筆記整理來源： 王爭 數(shù)據(jù)結(jié)構(gòu)與算法之美

總結(jié)

以上是生活随笔為你收集整理的【数据结构与算法】二分查找的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。