剑指 Offer 01. 二维数组中的查找

题目链接

二维数组中的查找

题目描述

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

解题思路

考察二分查找，借此题将二分查找的细节以及代码总结一下。

以防l+r溢出，可以设mid = l + (r - l) / 2;

AC代码

public class Solution {
    
    boolean Binary_search(int targe,int[][] array,int x, int y){
        int l = 0;
        int r = y-1;
        while(l <= r){
            int mid = (l + r) / 2;
            if(targe == array[x][mid]) return true;
            else if(targe > array[x][mid]){
                l = mid + 1;
            }
            else if(targe < array[x][mid]){
                r = mid - 1;
            }
        }
        return false;
    }
    
    public boolean Find(int target, int [][] array) {
        if(array.length == 0) return false;
        int xLen = array.length;
        int yLen = array[0].length;
        for(int i = 0; i < xLen; i++){
            if(Binary_search(target,array,i,yLen)){
                return true;
            }
        }
        return false;
    }
}