题解 | #二分查找某数#

#include <iostream>
#include <vector>
using namespace std;
//快速排序代码--这道题因为 给的数据是有序的的所以不用排序
void Mysort(vector<int>&a,int begin,int end){
    //左闭右开的
    if(begin==end){
        return;
    }
    int left=begin;
    int right=end-1;
    int temp=a[left];
    while(left<right){
        while(left<right&&a[right]>temp){
            right--;
        }
        a[left]=a[right];
        while(left<right&&a[left]<temp){
            left++;
        }
        a[right]=a[left];
    }
    a[left]=temp;
    Mysort(a,begin,left);
    Mysort(a,left,end-1);
 
}

//返回第一个出现的下标--那在这里使用二分来进行查找时间复杂度为log N
int Get(vector<int>&nums,const int &val){
    int left=0,right=nums.size();
    //使用左闭右开的区间范围，所以这里循环的终止条件是left==right [1,1)
    while(left<right){
        int mid=left+(right-left)/2;
        if(nums[mid]==val){
                    //等于val的时，那么我们就需要在[left,mid)这个区间继续找是否存在 ==val的值 找到左边界
            right=mid;
        }else if(nums[mid]>val){
            //如果mide>val时就在 [left,mid)区间查找，注意这里同样 左闭右开区间 nums[mid]>val;
            right=mid;
        }else if(nums[mid]<val){
                    //如果mid小于目标值，那么就在[mid+1,right)注意这里坚持了左闭右开  的区间原则
            left=mid+1;
        }
    }
    if(nums[left]==val){
        return left;
    }
    return -1;
}
int main(){
    //n几个数字，x目标值
    int n,x;
    cin>>n>>x;
    vector<int>arr;
    //用vector来保存输入的数据
    int temp;
    for(int i=0;i<n;i++){
         cin>>temp;
          arr.push_back(temp);
    }
   // Mysort(arr,0,arr.size());
    temp= Get(arr,x);
    cout<<temp;
    return 0;
}