题解 | #二分查找-II#

看到大家都喜欢用迭代的while来做，但是迭代看上去比较晕吧？我还是喜欢用递归的写法。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 如果目标值存在返回下标，否则返回 -1
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int search (int[] nums, int target) {
        // write code here

        int a = 0;
        int b = nums.length-1;
        if(nums.length>0){
            return binsearch(nums, 0, nums.length-1, target);
        }else{
            return -1;
        }

    }

    public int binsearch(int[] nums, int i, int j, int target){
        System.out.println("i="+i + ", j=" + j);

        if(j<i){
            return -1;
        }else if(j==i){
            return nums[i]==target?i : -1;
        }
        else{
            int k = i + (j-i)/2;
            if(nums[k]>target){
                System.out.println("k1=" + k);
                return binsearch(nums, i, k-1, target);
            }else if(nums[k]<target){
                System.out.println("k2=" + k);
                return binsearch(nums, k+1, j, target);
            }else{
                int firstFound = k;
                int tryfound = binsearch(nums, i, k-1, target);
                if(tryfound > -1){
                    return tryfound;
                }else{
                    return firstFound;
                }
            }
        }
    }
}