Toy14

rotatedArraySearch

부분적으로 오름차순 정렬 된 정수의 배열(rotated)과 정수(target)를 입력받아 target의 인덱스를 리턴해야 합니다.
O(logN) - 이진 탐색(binary search)을 약간 변형하여 해결

const rotatedArraySearch = function (rotated, target) {
  // TODO : 여기에 코드를 작성합니다.
  let left = 0
  let right = rotated.length-1
  while(left<=right){
    let mid = Math.floor((left+right)/2)
    if(target===rotated[mid]){
      return mid
    }if (rotated[left] < rotated[mid]) {
      // 왼쪽 절반이 정렬되어 있는 상태
      if (target < rotated[mid] && rotated[left] <= target) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      // 오른쪽 절반이 정렬되어 있는 상태
      if (target <= rotated[right] && rotated[mid] < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
  return -1;
};