[Algorithm] 9. Modified Binary Search

Darcy Daeseok YU ·2025년 3월 2일
0

Modified Binary Search

1.Search in Rotated Sorted Array (LeetCode #33)

function search(nums: number[], target: number): number {
  // O(n) X
  // return nums.indexOf(target);

  let left = 0,
    right = nums.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);

    if (nums[mid] === target) return mid;

    const isLeftSideSorted = nums[left] <= nums[mid];
    if (isLeftSideSorted) {
      // CASE1 :  left half is sorted
      // if (target >= nums[left] && target < nums[mid]) {

      const isTargetInLeft = target >= nums[left] && target < nums[mid];
      if (isTargetInLeft) {
        right = mid - 1; // Move left
      } else {
        left = mid + 1; // Move right
      }
    } else {
      // CASE2 :  Right half is sorted
      // if (target > nums[mid] && target <= nums[right]) {
      const isTargetInRight = target > nums[mid] && target <= nums[right];
      if (isTargetInRight) {
        left = mid + 1; // Move right
      } else {
        right = mid - 1; // Move left
      }
    }
  }

  return -1;
}

Recursive


function search(nums: number[],
  target: number,
  start: number = 0,
  end: number = nums.length - 1
): number {
  const mid = start + Math.floor((end - start) / 2);

  if (nums[mid] === target) {
    return mid;
  }

  if (end <= start) return -1;

  // Left half is sorted
  if (nums[start] <= nums[mid]) {
    if (nums[start] <= target && target < nums[mid]) {
      return search(nums, target, start, mid - 1);
    } else {
      return search(nums, target, mid + 1, end);
    }
  } else {
    if (nums[mid] < target && target <= nums[end]) {
      return search(nums, target, mid + 1, end);
    } else {
      return search(nums, target, start, mid - 1);
    }
  }
}

2.Find Minimum in Rotated Sorted Array (LeetCode #153)

function findMin(nums: number[]): number {
    let left = 0, right = nums.length -1 ; 

    let minIndex = nums.length - 1; 

    while (left <= right){


        const mid = left + Math.floor((right - left) / 2);

        if(nums[mid] <= nums[nums.length - 1]){
            minIndex = mid; 
            right = mid -1 ; 
        } else{
            left= mid + 1; 
        }

    }

    return nums[minIndex];
};

3.Search a 2D Matrix II (LeetCode #240)

both axes sorted in a ascending order : O(m + n)

// both axes sorted in a ascending order
function searchMatrixSimple(matrix: number[][], target: number): boolean {
  let r = 0,
    c = matrix[0].length - 1;
  while (r < matrix.length && c >= 0) {
    if (matrix[r][c] === target) return true;
    if (target > matrix[r][c]) {
      r++;
    } else {
      c--;
    }
  }
  return false;
}

O(M * logn) : for loop + binary search

  • finding indices [x,y]
// finding rowIndex and colIndex
function searchMatrix(matrix: number[][], target: number): number[] {
  const m = matrix.length;
  const n = matrix[0].length;

  for (let col = 0; col < n; col++) {
    const rowIndex = binarySearch(matrix[col], target);
    if (rowIndex !== -1) return [rowIndex, col];
  }

  return [-1, -1];
}

function binarySearch(rowArr: number[], target: number): number {
  let left = 0,
    right = rowArr.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (rowArr[mid] === target) return mid;

    if (rowArr[left] <= target && target < rowArr[mid]) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return -1;
}
profile
React, React-Native https://darcyu83.netlify.app/

0개의 댓글