二分查找

Meteor 2022-11-28 18:50:03
Categories： Tags：

704 二分查找

解题思路1

由于数组已经有序且每个值都不重复，因此可以采用二分法，而二分法既可以使用迭代也可以采用递归的方式。
迭代法：本题的关键在于确定边界条件，即while循环的条件是left<=right还是left<right，这取决于right初始值是nums.length还是nums.length-1，若right初始值为nums.length-1，则right参与运算，那么应采用left<=right，否则，应使用left<right。

代码

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length-1;
        int mid;
        while(left<=right){//若right初始值为nums.length，则应变为left<right
            mid = left + ((right-left)>>1);//防止left+right的和超出限制
            if(nums[mid]==target){
                return mid;
            }
            else if(nums[mid]>target){
                right = mid-1;//若right初始值为nums.length，则应变为right=mid;
            }
            else{
                left = mid+1;
            }
        }
        return -1;
    }
}

解题思路2

递归法：

代码

class Solution{
    public int search(int[] nums, int target){
        return dfs(nums, target, 0, nums.length);
    }
    public int dfs(int[] nums, int target, int left, int right){
        //若范围小于0，则已遍历完
        if(left>right) return -1;
        int mid = left+((right-left)>>1);
        if(nums[mid]==target) return mid;
        else if(nums[mid]>target) return dfs(nums, target, left, mid-1);
        else return dfs(nums, target, mid+1, right);
    }
}

总结

采用经典二分法的前提是数组有序且无重复值，分三种情况逐一处理即可。

层序遍历