题解 | #二维数组中的查找#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param target int整型
     * @param array int整型二维数组
     * @return bool布尔型
     */
    public boolean Find (int target, int[][] array) {
        //类似折半查找的思想，把矩阵以对角线分为上半区和下半区
        
        //不优化的方法，就是直接对每一行数组进行折半查找
        if(array == null||array.length==0){
            return false;
        }
        boolean result = false;
        for(int i=0;i<array.length;i++){
            result = result || binarySearch(array[i],target);
        }
        return result;

        //可以看成两个有序数组，一个纵向，一个横向

        //因为有序，可以使用二分查找

        //找到一个区间，target刚好在这两个数中间，而不是在其它的中间
        // if(array == null||array.length==0){
        //     return false;
        // }

        // int left = 0;
        // int right = array.length - 1;

        // while (left <= right) {
        //     int mid = (left + right) / 2;
        //     if (array[mid][0] == target) {
        //         return true;
        //     } else if (array[mid][0] > target) {
        //         right = mid - 1;
        //     } else {
        //         left = mid + 1;
        //     }
        // }
        //能执行到这里，说明没有数组头刚好相等的，只会处于，right和left之间的那个
        //就是right坐在哪一行
        // return binarySearch(array[right], target);
    }

    public boolean binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] == target) {
                return true;
            } else if (arr[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return false;
    }
}