二分法

二分法

---

题目

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

示例一

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

示例二

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

分析

1. 首先分析该数组为有序数组且为升序，同时可以判断得出该数组不存在重复的元素。即若存在相同的元素，则可能返回的不是唯一的元素下标。
2. 确定边界条件，即left<=right or left<right。 即保证若采用=，即使为左闭右闭条件，否则采用左边闭合右边开的条件。
3. 首先确定选择的类型 建议选择left<right类型，避免出现left = right 的无效空间。

算法逻辑

1. 首先确定 left = 0 与 right = nums.length;
2. 确定循环边界while(left < right),每次循环确定mid = left + ((right - left) >> 1)
3. 遍历nums[mid] 与 target 的大小，若> 则left = mid + 1;否则 right = mid;相等则返回mid。

Java 代码

采用left<=right边界条件

 public int search(int[] nums,int target){
        //左边闭合与右边闭合时 right 取nums.length - 1
        if(target < nums[0] || target > nums[nums.length - 1 ]){
            return -1;
        }
        int left = 0;
        int right = nums.length-1;
        while (left <= right){
            //获取当前数组的中间mid
            int mid = left + ((right - left) >> 1);
            if(nums[mid] == target){
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            }
        }
        return -1;
    }

采用left<right边界条件

 public int search_2(int[] nums,int target){
        //左边闭合且右边开时  right = nums.length  这种情况下不会出现right = left情况
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + ((right - left) >> 1); 
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid;
        }
        return -1;
    }

题目推荐

1. 搜索插入位置
2. 在排序数组中查找元素的第一个和最后一个位置