話不多說，先來段二分查找的代碼。 #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> int BinSearch(int arr[], int sz, int key){//找到返回下標，找不到返回-1int left = 0;int right = sz - 1;while (left <= right){int mid = left + ((right - left) >> 1);if (key < arr[mid]){right = mid - 1;}else if (key>arr[mid]){left = mid +1;}elsereturn mid;}if (left > right)return -1; } int main() {int arr[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };int sz = (sizeof(arr) / sizeof(arr[0]));int a = 1;int ret=BinSearch(arr, sz, a);printf("%d\n", ret);getchar();return 0; }首先，要求二分查找的時間復雜度就要知道什么是時間復雜度，時間復雜度其實就是一個函數，該函數計算的是執行基本能操作最壞的次數，在二分查找中，二分的次數就是基本語句的執行次數，我們不妨設次數為x,假設該數組的長度是n,一次二分后長度變為n/2,兩次二分后長度變為n/4,........x次二分后長度變為n/(2)^x,假設最壞長度變為1才找到了key,此時可得(n/(2)^x)=1;可得x=log2n(log以2為底n的對數)，而在數據結構中常常這樣寫lgn,所以o()=o(lgn);

總結

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

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