思考題：假設有 1000 萬個整數數據，每個數據占 8 個字節，如何設計數據結構和算法，快速判斷某個整數是否出現在這 1000 萬數據中？希望不要占用太多的內存空間，最多不要超過 100MB

二分思想

查找算法	? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?特點
二分查找	1、二分查找針對的是一個有序的數據集合，查找思想有點類似分治思想。每次都通過跟區間的中間元素對比，將待查找的區間縮小為之前的一半，直到找到要查找的元素，或者區間被縮小為 0。 2、時間復雜度O(logn)的 查找速度

對數時間復雜度在大數據量級的情況下有時候比常量級別查找速度O(1）還要高效

二分查找的實現

假設數組中不存在重復的元素：

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

注意循環退出條件

注意mid的取值：mid=(low+high)/2 這種寫法是有問題，如果high和low都比較大容易造成內存溢出。改進的寫法是：mid 的計算方式寫成 low+(high-low)/2；更進一步提升性能的寫法：可以將這里的除以 2 操作轉化成位運算 low+((high-low)>>1)

low和high的更新：low=mid+1，high=mid-1

二分查找的應用局限性

二分查找依賴的是順序表結構，簡單點說就是數組。二分查找只能用在數據是通過順序表來存儲的數據結構上。如果你的數據是通過其他數據結構存儲的，則無法應用二分查找

二分查找針對有序數據：如果數據沒有序，我們需要先排序。排序的時間復雜度最低是 O(nlogn)。因此對于插入、刪除操作不頻繁，一次排序、多次查找的場景，比較適合二分查找。

針對動態變化的數據集合二分查找不再適合。

數據量太大不適合二分查找：二分查找依賴數組結構，數組為了隨機訪問特性，對內存空間的連續性要求較高，如果剩余空間無法滿足，那么無法使用二分查找

查找算法	? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 局限性
二分查找	1、依賴數組，如果數據存在鏈表上，不能使用 2、依賴數組，對內存空間有要求，如果剩余連續空間過小，數據量大，也不能用二分查找 3、動態變化的數據不適合用二分查找（還是因為數據結構的特點對插入、刪除操作不友好，維護成本太高） 4、對于插入、刪除操作較少（或者是歷史靜態數據），一次排序多次查找適合二分查找

?

回答開篇

內存限制是 100MB，每個數據大小是 8 字節，最簡單的辦法就是將數據存儲在數組中，內存占用差不多是 80MB，符合內存的限制。借助今天講的內容，我們可以先對這 1000 萬數據從小到大排序，然后再利用二分查找算法，就可以快速地查找想要的數據了。

用散列表和二叉樹是無法解決的原因：

• 散列表、二叉樹這些支持快速查找的動態數據結構。用散列表和二叉樹實際上是不行的。大部分情況下用二分查找可以解決的問題，用散列表、二叉樹都可以解決。但是，不管是散列表還是二叉樹，需要比較多的額外內存空間。
• 如果用散列表或者二叉樹來存儲這 1000 萬的數據，用 100MB 的內存肯定是存不下的。而二分查找底層依賴的是數組，除了數據本身之外，不需要額外存儲其他信息，是最省內存空間的存儲方式，所以剛好能在限定的內存大小下解決這個問題

總結

以上是生活随笔為你收集整理的15 | 二分查找（上）：如何用最省内存的方式实现快速查找功能？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。