【Leetcode Daily】704二分查找

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个升序不重复的整型数组和一个目标值 target，找出 target 在数组中的下标，若 target 不存在，则返回 -1.

思路分享

• 看似与【Leetcode Daily】35搜索插入位置相似，但有一个需要特别注意的地方，那就是本题在搜索完成后，需要取左指针 left 对应的值来查看 target 是否存在。

• 这个就会要求 left 指针应当不超过数组边界，因为此前的基本思路中（【Leetcode Daily】34在排序数组中查找元素的第一个和最后一个位置只能保证 left 指针的左侧所有下标元素均小于目标值，而不能保证 left 指针本身合法。

• 换句话，如果数组中所有元素小于目标值，那么 left 指针就会滑到 nums.size() 这个下标处，而下标的最大值是 nums.size()-1，就可能会不合法，需要在检测 target 是否存在前，先检测 left 是否合法。

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size();
        while(left < right) {
            int middle = left+(right-left)/2;
            if (nums[middle] < target) {
                left = middle+1;
            }
            else {
                right = middle;
            }
        }
        return (left < nums.size() && nums[left]==target) ? left : -1;
    }
};