package com.wujunshen.algorithm.leetcode.divide.conquer;

/**
 * @author frank woo(吴峻申) <br>
 *     email:<a href="mailto:frank_wjs@hotmail.com">frank_wjs@hotmail.com</a> <br>
 * @date 2022/7/25 21:02<br>
 */
public class 搜索二维矩阵II {
  public boolean searchMatrix(int[][] matrix, int target) {
    for (int[] row : matrix) {
      int index = search(row, target);
      if (index >= 0) {
        return true;
      }
    }
    return false;
  }

  public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
      int mid = left + (right - left) / 2;
      int num = nums[mid];
      if (num == target) {
        return mid;
      } else if (num > target) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    return -1;
  }
}