Learning Journal

2/24/2024

Search a 2D Matrix

function searchMatrix(matrix: number[][], target: number): boolean {
    let lo = 0, hi = matrix.length - 1;
    let mid = Math.floor((lo + hi)/2)
    let midArr = matrix[mid];
    
  while(lo <= hi) {
      if(midArr[0] > target){
        hi = mid - 1;
        mid = Math.floor((lo + hi)/2)
        midArr = matrix[mid];
      }
      else if (midArr[midArr.length - 1] < target) {
        lo = mid + 1;
        mid = Math.floor((lo + hi)/2)
        midArr = matrix[mid];
      }
      else
        break;
  }
  

  if(lo > hi) return false;

  return binarySearch(mid);
  

  function binarySearch(row:number):boolean {
      const arr = matrix[row];

      let lo = 0, hi = arr.length - 1;

      while(lo <= hi) {
          const mid = Math.floor((lo + hi)/2);

          if(arr[mid] < target) {
              lo = mid + 1;
          }
          else if(arr[mid] > target) {
              hi = mid - 1;
          }
          else {
              return true;
          }
      }
      

      return false;

  }  
};function searchMatrix(matrix: number[][], target: number): boolean {
    let lo = 0, hi = matrix.length - 1;
    let mid = Math.floor((lo + hi)/2)
    let midArr = matrix[mid];
    
  while(lo <= hi) {
      if(midArr[0] > target){
        hi = mid - 1;
        mid = Math.floor((lo + hi)/2)
        midArr = matrix[mid];
      }
      else if (midArr[midArr.length - 1] < target) {
        lo = mid + 1;
        mid = Math.floor((lo + hi)/2)
        midArr = matrix[mid];
      }
      else
        break;
  }
  

  if(lo > hi) return false;

  return binarySearch(mid);
  

  function binarySearch(row:number):boolean {
      const arr = matrix[row];

      let lo = 0, hi = arr.length - 1;

      while(lo <= hi) {
          const mid = Math.floor((lo + hi)/2);

          if(arr[mid] < target) {
              lo = mid + 1;
          }
          else if(arr[mid] > target) {
              hi = mid - 1;
          }
          else {
              return true;
          }
      }
      

      return false;

  }  
};

THE PROBLEM

In the first attempt, I went over the rows from index 0 and checked one by one to see if the elements were in the range of the row; then, when I found the correct row, I performed the binary search on that row. Even though I skipped all of the rows whose ranges do not contain the element, I still need to check them one by one.

So, in the second attempt, I made an improvement by doing binary search on the range created by rows to see which row the element belongs to. Basically, I pick the mid rows, if the element is smaller than the first element of the mid row, it means it should be in the first half. Otherwise, if it is greater than the last element of the mid row, it means it should be in the second half. The loop terminates in either one of two conditions: the lo and 'hi pointer cross each other or the element is in the range of the mid row. In the first condition, the lo and hi pointer cross but the algorithm still cannot find the element, which means the element is not in the matrix.

Revised by ChatGPT

In my initial approach, I iterated over the rows from index 0, checking if the target was within the range of each row. Once the correct row was identified, I performed a binary search on that row. Although this method skipped rows that couldn't contain the target, it still required checking each row sequentially.

To improve efficiency, I implemented a binary search on the ranges defined by the rows. I selected the middle row and compared the target with the first and last elements of that row. If the target was smaller than the first element, it meant the target could only by in the first half of the matrix. Conversely, if the target was larger than the last element, it indicated that the target could only be in the second half. The loop terminated under two conditions: either the lo and hi pointers crossed each other, or the target was found to be within the range of the middle row. If the pointers crossed without finding the target, it meant that the target was not present in the matrix.

The algorithm works because it effectively utilizes binary search in two stages to efficiently locate the target value in the matrix:

Finding the Correct Row:

The matrix is sorted both row-wise and column-wise. This means that the first element of each row is greater than the last element of the previous row.
By performing a binary search on the first elements of each row, you can quickly identify the row that might contain the target value. This is because if the target value is greater than the first element and less than the last element of a row, it must be within that row.
If the binary search concludes without finding a suitable row (i.e, lo > hi), it means the target value is not present in any row, and thus not in the matrix. 2 Searching Within the Row:
Once the correct row is identified, a standard binary search is performed within that row to find the target value.
If the value is found, the function returns true; otherwise, it returns false after exhausting all possibilities in the row.

By leveraging the sorted nature of the matrix and using binary search twice, the algorithm significantly reduces the search space at each step, making it efficient and correct for this problem.