[Binary Search] Search in Rotated Sorted Array

33. Search in Rotated Sorted Array

지문은 링크에서 확인해주세요.

1. 해답을 보지 않고 스스로 문제를 해결한 과정

본 문제는 해결하지 못했습니다.

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  if (left === right && nums[0] === target) {
    return 0;
  }

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

    if (nums[mid] === target) {
      return mid;
    }    
    
    const leftSideMaxDx = Math.abs(target - nums[mid - 1]);
    const rightSideMaxDx = Math.abs(target - nums[right]);   

    if(leftSideMaxDx > rightSideMaxDx) {
      left = mid;      
    } else {
      right = mid;      
    }                
  }

  return -1;
};

중간 인덱스를 기준으로 좌측과 우측 영역을 나눕니다. 각 측의 최댓값이 target과 얼마나 차이가 적은지를 확인하여 divide 되는 영역을 결정합니다. 단, 본 해답은 다음과 같은 테스트케이스를 통과하지 못했습니다. 즉, target이 nums에 없으면 해결할 수 없는 로직입니다.

Input:	nums = [1,3], target = 0
Output: Time Limit Exceeded
Expected: -1

2. 여러 해답을 직접 찾아서 자신이 작성한 알고리즘에 대해서 회고한 내용

2-1. Using binary search with more condition

해답의 전문은 링크를 확인해주세요.

/**
 * Runtime	: 57 ms
 * Memory	: 41.18 MB
 */
var search = function(nums, target) {
  let left = 0;
  let right = nums.length - 1;
    
  while (left <= right) {
    let mid = Math.floor((left + right) / 2); 
    
    if (nums[mid] === target) {
      return mid;
    }
    
    // When dividing the roated array into two halves, one must be sorted.
    
    // Check if the left side is sorted
    if (nums[left] <= nums[mid]) {
      if (nums[left] <= target && target <= nums[mid]) {
        // target is in the left
        right = mid - 1;
        
      } else {
        // target is in the right
        left = mid + 1;
      }
    } 
    
    // Otherwise, the right side is sorted
    else {
      if (nums[mid] <= target && target <= nums[right]) {
        // target is in the right
        left = mid + 1;

      } else {
        // target is in the left
        right = mid - 1;
      }
    }
  }
    
  return -1;
};

left 또는 right 측이 만약 정렬된 상태라면, 양측에 target은 존재한다. 라는 점을 보아서 필자와 접근은 비슷하지만, 더 면밀한 조건을 찾은 해답입니다.