折半查找算法介紹

折半查找（Binary Search）又稱為二分查找。它的前提是線性表中的記錄必須是關鍵碼有序（通常從小到大有序），線性表必須采用順序存儲。從算法名稱可以看出算法的思路，先取有序序列中間值與查找值進行比較，中間值小于查找值 就查找后一子表，如果中間值大于查找值 就查前移子表，直到查找到或者子表不存在為止。由于折半查找的查找范圍是成倍的縮寫，所以折半查找法的算法時間復雜度為logn。

折半查找算法代碼

代碼簡單喲，因為我們并不知道循環(huán)次數(shù)，所以優(yōu)先采用的while 循環(huán)，當然for、while、do while 循環(huán)都可以相互轉換的哈。

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> //折半查找法 arr數(shù)組，length 數(shù)組長度，key 查找的關鍵字 //返回查找值的下標 ，沒查找到 返回-1 int Binary_Search(int *arr, int length, int key) {int low = 0;//低位下標int high = length-1;//高位下標int mid;//中間值下標while (low <= high){mid = (low + high) / 2;if (key < arr[mid]){high = mid - 1;}else if(key > arr[mid]){low = mid + 1;}else{return mid;}}return -1; } int main(int argc, char *argv[]) {int arr[10] = { 0,1,2,3,4,5,6,7,8,9};int index1 = Binary_Search(arr, 10, 5);int index2 = Binary_Search(arr, 10, 100);printf("index1 = %d，index2 = %d\n",index1,index2);return 0; }

運行結果檢測

總結

以上是生活随笔為你收集整理的查找算法：折半查找算法实现及分析的全部內容，希望文章能夠幫你解決所遇到的問題。

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