leetcode704-二分查找

• 题目描述
• 代码
• 解题思路

给定一个 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        

提示：

1. 你可以假设 nums 中的所有元素是不重复的。
2. n 将在 [1, 10000]之间。
3. nums 的每个元素都将在 [-9999, 9999]之间。

class Solution {
    public int search(int[] nums, int target) {
        return search(0, nums.length - 1, nums, target);
    }

    public int search(int low, int high, int[] nums, int target) {
        
        if (low <= high) {
            int avg = (low + high) >> 1;
            if (nums[avg] == target) {
                return avg;
            } else if (nums[avg] < target) {
                return search(avg + 1, high, nums, target);
            }
            return search(low, avg - 1, nums, target);
        }
        return -1;
    }
}

我这里使用的是递归

1. 当low > high的时候,说明已经超越数组的边界了,这时的target一定是不存在的;
2. 当low <= high的时候，此时取当前数组min下标+max下标的平均值,然后让平均值下标与target进行比较，此时共有三种情况
   • 此下标的值就是target，直接返回此下标
   • 此下标的值小于target, 说明target可能位于[avg + 1, high]的区间里,再递归这个区间，传递相应的参数
   • 最后就是当前下标的值大于target, 说明target可能位于[low, avg - 1]的区间里，递归这个区间，传递相应的参数。

力扣题目链接