1.问题出处

2.我的解法

解法一

用循环不断缩小查找的范围，以题目原本的案例为例

public int search (int[] nums, int target) {
        // write code here
        int left = 0;
        int right = nums.length - 1;
        while (true){
        //已经遍历完整个数组都没找到目标值
            if (left > right){
                return -1;
            }
            int mid = (left+right)/2;
            if (nums[mid] > target){
//            答案有可能在前半段，改变右边界
                right = mid-1;
            } else if (nums[mid] < target) {
//                答案有可能在后半段，改变左边界
                left =mid + 1;
            } else if (nums[mid] == target) {
            //找到答案啦，返回下标
                return mid;
            }else {
            //前面的情况都不满足，即没找到答案，返回-1
                return -1;
            }

        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

解法二

用递归，其实和上面解法一是一样的

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

    private int findTarget(int[] nums,int left,int right, int target){
        int mid = (left+right)/2;
//        递归出口
        if (nums.length<=0 || left > right){
            return -1;
        }
        if (nums[mid] == target){
            return mid;
        }
//        递归条件
        if (nums[mid] > target){
            return findTarget(nums,left,mid-1,target);
        } else if (nums[mid] < target) {
            return findTarget(nums,mid+1,right,target);
        }else {
            return -1;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22