演算法簡介：二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法，但是，折半查找要求線性表必須采用順序存盤結構，而且表中元素按關鍵字有序排列
使用前提：文章已經按升序排列
基本原理：(只要滿足left<=right就一直回圈執行以下流程)
首先將要尋找的元素（k）與陣列的中間元素比較
1.如果 k 小于中間元素，只需在陣列的前一半元素中繼續尋找
2.如果 k 和中間元素相等，匹配成功，查找結束
3.如果 k 大于中間元素，只需在陣列的后一半元素中繼續尋找
我們假設被查找的數字位于如下陣列中：
//假設被查找數字為8
int arr[11]={1,2,3,4,5,6,7,8,9,10,11};
首先將要尋找的元素（k）與陣列的中間元素比較(mind = (left+right) / 2)
不難發現，被查找的值8大于中間元素6
只需在陣列的后一半元素中繼續尋找（將 left 賦值為 mind +1）
再次修改mind的值（mind = (left+right) / 2）
再次比較，被查找的值8小于中間元素9
只需在陣列的前一半元素中繼續尋找（將 right 賦值為 mind -1）
再次修改 mind 的值（mind=(left+right)/2 = 7）
被查找的值8大于中間元素9
在陣列的后一半元素中繼續尋找，將 left 賦值為 mind + 1
再次執行 mind = ( left+right) / 2
此時 mind 的值已經等于尋找到值（下表為7），回圈結束，停止尋找，
代碼實作：
#include<stdio.h`>
int main()
{
int arr[] = { 1,2,3,4,5,6,7,8,9,10,11 };
int left = 0;//左下標
int right = sizeof(arr) / sizeof(arr[0])-1;//右下標
int k = 8;//陣列中尋找的值
int mind = 0;
while (left <= right)
{
mind = (left + right) / 2;
if (arr[mind] > k)//中間元素小于尋找的值，移動右下標
{
right = mind - 1;
}
else if (arr[mind] < k)//中間元素大于尋找的值，移動左下標
{
left = mind + 1;
}
else
break;
}
if (left <= right)
{
printf("找到了，下表是%d\n", mind);
}
else
printf("找不到\n");
return 0;
}
//實作一個二分查找函式
int bin_search(int arr[], int left, int right, int k)
{
int mind = 0;
while (left <= right)
{
mind = (left <= right)/2;
if (arr[mind] > k)
{
right = mind - 1;
}
else if (arr[mind] < k)
{
left = mind + 1;
}
else
return mind;//找到了，回傳下表
}
return -1;//找不到,此時回傳的值不可以在陣列坐標的取值范圍內
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/293778.html
標籤：其他
上一篇：嵌入式開發中的防御性C語言編程