基本的二分查找

非递归

public int binarySearch(int []nums ,int target)
    {
        int low=0;
        int high=nums.length-1;
        int mid;
        while (low<=high)
        {
            mid=low+(high-low)/2;
            if (target==nums[mid])return mid;
            if (target>nums[mid])low=mid+1;
            if (target<nums[mid])high=mid-1;
        }
        return -1;
    }

递归

int binarysearch(int array[], int low, int high, int target) {
    if (low > high) return -1;
    int mid = low + (high - low) / 2;
    if (array[mid] > target)
        return binarysearch(array, low, mid - 1, target);
    if (array[mid] < target)
        return binarysearch(array, mid + 1, high, target);
    return mid;
}

下面是一个二分查找的变种题目
leetcode 74 二分查找一个二维矩阵 二维矩阵有序

 public boolean searchMatrix(int[][] matrix, int target) {
        return binarySearch(matrix,0,matrix.length*matrix[0].length,target);
    }
    public boolean binarySearch(int [][] array,int left,int right,int target)
    {
        if (left>=right)return false;
        int mid=(left+right)>>1;
        int row=mid/array[0].length;
        int col=mid%array[0].length;
        if (target>array[row][col])return binarySearch(array,mid+1,right,target);
        else if (target<array[row][col])return binarySearch(array,left,mid,target);
        else return true;
    }

核心思想就把当前的位置转化为对应的行和列 然后正常按照二分查找的思想来学就行了 在设置left和right的时候 注意一个问题 如果设置的right是无法访问到的index 那判断条件就是if(left>=right)retrun false;
例如 array[8] 最先开始搜索的 right=8 是无法访问到的
所以应该按照下面这样写

 if (target>array[row][col])
return binarySearch(array,mid+1,right,target);
else if (target<array[row][col])
return binarySearch(array,left,mid,target);

如果我设置初始的right=len-1的话
那就是下面这样写的

 if (target>array[row][col])
return binarySearch(array,mid+1,right,target);
else if (target<array[row][col])
return binarySearch(array,left,mid-1,target);