先貼上二分查找的java代碼實現

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

時間復雜度，其實就是分析代碼執行的次數。
in low = 0和int high = n - 1就不說了，都是常量級的執行時間，對總的執行時間影響不大。
關鍵是while循環中的代碼執行次數是多少次？
while循環的代碼，很簡單，就是每次取中間的數和目標值進行比較。我們來分析一下執行的過程
第一次：n/2
第二次：n/22
第三次：n/23
。
。
。
。
第k次：n/2的k次方
可以看到每比較一次，數據量就減少一半。最壞的情況下，直到待查找數組只剩最后一個元素時，才匹配到目標值。此時待比較的數據量就只剩1個。
輸入法不好打出對數和k次方，所以此處借用極客時間的一張圖。來說明一下

所以二分搜索的時間復雜度是O(logn)

總結

以上是生活随笔為你收集整理的二分搜索的时间复杂度分析的全部內容，希望文章能夠幫你解決所遇到的問題。

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