问题：在数组中查找某一个数字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;//右移一位即除以2if(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;
}