题解 | #二分查找-I#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
     //试试可不可以用find-> find可以  但是本题要求的是用二分查找
     //
    // int search(vector<int>& nums, int target) {
    //     auto it = find(nums.begin(),nums.end(),target);
    //     if(it == nums.end()){
    //         return -1;
    //     }
    //     return it-nums.begin();
    //     // write code here
    // }
    //二分查找 指针
        int search(vector<int>& nums, int target) {
        int left,right,mid;
        left = 0,right = nums.size()-1,mid =(right + left) /2;
        //vector数组可以用下标随意访问
        while(left<=right)
        {
            if(target == nums[mid]) return mid;
            if(target < nums[mid]){right = mid-1;}
            else{
                left = mid+1;
            }
            mid = (right+left)/2;
        }
        return -1;
        // write code here
    }
};

二分查找： 用指针的思想。

定义三个指针，分别指向数组起始位置（left)、数组的中间位置(mid)、数组最后一元素的位置(right)。

因为给的nums是一个有序的数组，可以用“二分” 的思想。

每次比较target和mid位置。会有两种情况

1.target和nums[mid]的值相同，则直接返回mid，程序退出；

2.target<nums[mid]，说明想要查找的值在mid的左半区，此时则需要更新right和mid的位置，right = mid-1,

target>nums[mid]，说明想要查找的值在mid的右半区，此时则需要更新left和mid的位置，left= mid+1,

再更新mid的位置。