二分算法（查找）

问题：在数组中查找某一个数字x=4的下标

例：arr:1        3        4        6        10        20        21        22

显然，数字4的下标为3。

1、线性查找，一个个地去遍历，时间复杂度为O(n)

2、二分查找，时间复杂度为O(logn)        前提：arr一定要单调

 下面具体介绍二分查找：

现在，L=1，R=8（要查找的数组范围，数组下标从1开始）

mid=（L+R）/ 2 =4，arr[mid]=6        大于4，更新R=mid-1（因为是单调的）

L=1，R=3

mid=（L+R）/ 2 =2，arr[mid]=3        小于4，更新L=mid+1

L=3，R=3

mid=（L+R）/ 2 =3，arr[mid]=4        等于4，找到了

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100;
int arr[N];
int binarySearch(int arr[],int n,int x){
	sort(arr+1,arr+n+1);//先排序
	int L=1,R=n;
	int ans=-1;
	while(L<=R){
		int mid=(L+R)>>1;//右移一位即除以2
		if(arr[mid]==x){
			ans=mid;
			break;
		}
		if(arr[mid]>x){
			R=mid-1;
		}else{
			L=mid+1;
		}
	} 
	return ans;
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	int x;
	cin>>x;//要查找的数字 
	
	cout<<binarySearch(arr,n,x)<<endl;
	return 0;
}