如果這篇文章對你有所幫助或者給了你靈感，歡迎給我點個小紅心，如果沒有，也可以點個贊支持一下，謝謝大家！！！
二分法
基本思想：
假設資料是按升序排序的，對于給定值key，從序列的中間位置 k 開始比較，
如果當前位置arr[k]值等于key，則查找成功；
若key小于當前位置值arr[k]，則在數列的前半段中查找,arr[low,mid-1]；
若key大于當前位置值arr[k]，則在數列的后半段中繼續查找arr[mid+1,high]，
時間復雜度：
1.最壞情況查找最后一個元素（或者第一個元素）Master定理T(n)=T(n/2)+O(1)所以T(n)=O(log2n)
2.最好情況查找中間元素O(1)查找的元素即為中間元素（奇數長度數列的正中間，偶數長度數列的中間靠左的元素）
下面給出具體代碼：
#include<stdio.h>
#include<string>
int main()
{
int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int x;
printf("請輸入你要查找的數字:\n");
scanf("%d", &x);
int right = sizeof(a) / sizeof(a[0]) - 1;
int left = 0;
while (left <= right){
int mid = (left + right) / 2;
if (x > a[mid]){
left = mid + 1;
}
else if (x < a[mid]){
right = mid - 1;
}
else{
printf("找到了，下標是：%d\n", mid);
break;
}
}
if (left>right)
printf("找不到\n");
}
下圖為運行結果：
都看到這了，就點個贊支持一下唄！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/230642.html
標籤：其他
上一篇：雜談：玩玩24點