大前端

题目：

---

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9     
输出: 4       
解释: 9 出现在 nums 中并且下标为 4     

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2     
输出: -1        
解释: 2 不存在 nums 中因此返回 -1        

思路

---

该题目给出该数组为有序，并且强调没有重复元素，否则查找出的元素下表一定不唯一，因此如果符合这两个条件，我们就可以用二分查找。
写二分法的区间的定义，一般有两种写法，左闭右闭即[left, right]，或者是左闭右开即[left, right)。

二分法的第一种写法

第一种写法，也就是左闭右闭的写法[left, right]，因此需要注意一下：

• while(left <= right) 要使用 <=，因为 left == right 是有意义的

public int search(int[] nums, int target) {

        //有序miss-
        if (target > nums[nums.length - 1] || target < nums[0]){
            return -1;
        }

        int low = 0, high = nums.length - 1;
        while (low <= high){
            int mid = low + (high - low) >> 1;
            if (mid < target){
                low = mid + 1;
            }else if (mid > target){
                high = mid - 1;
            }else {
                return mid;
            }
        }
        return -1;
    }

第二种写法

也就是[left, right]
代码如下：

public int search(int[] nums, int target) {

        if(nums[0] > target || nums[nums.length - 1] < target)
            return -1;

        int low = 0, high = nums.length;
        while (low < high){

            //miss-
            int mid = low + (high - low) >> 1;
            if(target < nums[mid]){
                high = mid - 1;
            }else if (target < nums[mid]){
                low = mid + 1;
            }else {
                return mid;
            }
        }
        return -1;
    }

本题重点

对 low，high 的边界处理