二分法查找

算法目的:

​ 其輸入是一個有序的元素清單。如果要查找的元素包含在清單中，二分查找傳回其位置；否則傳回-1。

算法思想:

​ 通過折中（二分），縮小其被查找的範圍，來查詢其值的位置。在資料量較大時，更适用。

設定三個索引，分别為 L (左邊界索引) 、R （右邊界索引）、 LR （中間索引）

将中間索引 LR 所對應的數組值與查找值 k 進行比較

當其值相等時 ----表示找到其位置 傳回索引LR

當不相等時 判斷A[LR] 是 比 k 大還是小

通過判斷結果更新 左右索引

當左索引（L）大于右索引 ( R) 表示 查詢結束 為找到查詢目标 （傳回-1）

動态示範：

算法代碼:

​ 時間複雜度 （log n）

#include<iostream>
#include <vector>
using namespace std;
//二分法查找有序數組中索引位置
int Erfenfa(vector<int> A, int k)
{
	//擷取數組長度
	int len = A.size();
	//設定左右索引
	int l = 0, r = len - 1;
	//元素個數 為0 傳回-1
	if (l > r)
		return -1;
	//元素個數為一 判斷傳回目前索引/-1
	if (l == r)
		return A[l] == k ? 0 : -1;
	//數組中間索引（用來取代左右索引）
	int lr = (l + r) / 2;
	//判斷數組升降序 
	//降序
	if (A[l] > A[r])
	{
		while (l <= r)
		{
			//找到索引 傳回
			if (A[lr] == k)
				return lr;
			//更新左右索引 縮小範圍
			A[lr] > k ? l = lr + 1 : r = lr - 1;
			//更新lr
			lr = (l + r) / 2;
		}
	}
	//升序
	else
	{
		while (l <= r)
		{
			//找到索引 傳回
			if (A[lr] == k)
				return lr;
			//更新左右索引 縮小範圍
			A[lr] > k ? r = lr - 1 : l = lr + 1;
            //更新lr
			lr = (l + r) / 2;
		}
	}
	//未找到 傳回-1
	return -1;
}
int main()
{
	//簡單測試
	//注: 元素不能重複
	//若有重複 找到的結果為 目标值所在的多個索引的其中一個索引
	vector<int> A = { 1,2,3,6,7,8,9 };
	vector<int> B = { 9,8,7,6,5,4,3,2,1,-1,-2,-3 };
	cout << Erfenfa(A, 5) << endl << Erfenfa(B, -4);
	return 0;
}