부분 오름차순 정렬된 배열이 있을 때, 입력받은 요소의 인덱스를 리턴하라.

시간복잡도는 O(logN).

입출력 예)

let output = rotatedArraySearch([4, 5, 6, 0, 1, 2, 3], 2);
console.log(output); // --> 5

output = rotatedArraySearch([4, 5, 6, 0, 1, 2, 3], 100);
console.log(output); // --> -1

내가 쓴 코드: 테스트케이스는 통과하는데 O(N) 연산 때문에 막힌 걸로 생각됨.

어떻게 레퍼런스처럼 생각해낼수 있는지 모르겠다. 전혀!!!

const rotatedArraySearch = function (rotated, target) {
  // TODO : 여기에 코드를 작성합니다.

  //이진 탐색으로 최솟값의 인덱스 구한다. 그것을 a라고 하면 a를 아래에서 활용한다. 
  //최솟값은 바로 앞의 값보다 작고, 뒤의 값보다도 작다.

    let startIndex = 0;
    let endIndex = rotated.length - 1;

    while (startIndex <= endIndex) { //더 이상 배열을 절반으로 나눌 수 없을 때까지 반복한다.
      const middleIndex = startIndex + Math.floor((endIndex - startIndex) / 2);
      if (rotated[middleIndex] === target) {
        return middleIndex; //해당 요소가 존재시 바로 리턴.
      }
      if (rotated[middleIndex] < target) {
        startIndex = middleIndex + 1; //찾는 값이 middle보다 더 큰 경우 검색범위를 middle 이상으로 하기
      } else {
        endIndex = middleIndex - 1;
      }
    }

  
    while (startIndex <= endIndex) { //더 이상 배열을 절반으로 나눌 수 없을 때까지 반복한다.
      const middleIndex = rotated[rotated.length - 1];
      if (rotated[middleIndex] === target) {
        return middleIndex; //해당 요소가 존재시 바로 리턴.
      }
      if (rotated[middleIndex] < target) {
        startIndex = middleIndex + 1; //찾는 값이 middle보다 더 큰 경우 검색범위를 middle 이상으로 하기
      } else {
        endIndex = middleIndex - 1;
      }
    }
  
    return -1; //해당 요소가 배열에 없을 시 -1을 리턴한다.
};

레퍼런스

일단 반으로 나누면 무조건 한쪽은 정렬이 되어 있을 거고 나머지는 정렬이 되어 있지 않을 것이다.

const rotatedArraySearch = function (rotated, target) {
  // TODO : 여기에 코드를 작성합니다.
  let start = 0;
  let end = rotated.length - 1;
  while(start <= end){
    const mid = Math.floor((end + start) / 2);

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

    if(rotated[start] < rotated[mid]){ 
//정렬 여부는 양 말단 값의 대소 비교를 통해 가능하다.(토이8)
      //왼쪽 정렬된 상태
      if(target >= rotated[start] && target < rotated[mid]){
        end = mid - 1;
      }else{
        start = mid + 1;
      }
    }else{
      //오른쪽 정렬된 상태
      if(target > rotated[mid] && target <= rotated[end]){
        start = mid + 1;
      }else{
        end = mid - 1;
      }
    }
  }
  return -1;
};

[9,8,1, 2 ,3,4,5]에서 9 찾기