Algorithm problem-14

1. 문제

• 부분 오름차순 정렬된 배열을 받아, target의 인덱스를 리턴
• 없는 경우는 -1 리턴

2. 시도

• 부분 정렬이 무작위로 포인트가 잡혔다고 생각하였음
• 가장 작은 수를 찾아 포인트로 잡고, 0번 인덱스부터 포인트-1까지를 전반부
• 포인트부터 끝까지를 후반부로 나눠 타겟의 범위를 줄이고 시작하였음
• 타겟이 전반부 또는 후반부의 범위에 따라, 따로 while문으로 BinarySearch를 하였음
• 부분 정렬이 내 생각대로 무작위였다면 가장 효율적이였겠으나, 문제에 주어진 포인트는 중간점의 +-1 범위 내에 포인트가 있었음
• 결국 효율성 문제로 마지막 문제를 해결하지 못했음

3. 수도코드

const rotatedArraySearch = function (rotated, target) {
  // 가장 작은 수를 중간점으로 잡고
  let mid = rotated.indexOf(Math.min(...rotated))
  let start = 1;
  let end = rotated.length - 1;
  // 0번 인덱스랑 같으면 0번 리턴
  if (target === rotated[0]) {return 0;}
  // 0번 인덱스보다 크면 1번 인덱스부터 중간점 -1 까지 서치
  else if (target > rotated[0]) {
    end = mid - 1;
    while (start <= end) {
      let cur = parseInt((start + end) / 2);
      if (target > rotated[cur]) {
        start = cur + 1;
      }
      else if (target < rotated[cur]) {
        end = cur - 1;
      }
      else if (target === rotated[cur]) {
        return cur;
      }
    }
    return -1;
  }
  // 0번 인덱스보다 작으면 중간점부터 끝까지 서치
  else if (target < rotated[0]) {
    start = mid;
    while (start <= end) {
      let cur = parseInt((start + end) / 2);
      if (target > rotated[cur]) {
        start = cur + 1;
      }
      else if (target < rotated[cur]) {
        end = cur - 1;
      }
      else if (target === rotated[cur]) {
        return cur;
      }
    }
    return -1;
  }
  return -1;
};

4. 레퍼런스

const rotatedArraySearch = function (rotated, target) {
  let start = 0; // 처음의 시작은 0번부터
  let end = rotated.length - 1; // 처음의 끝은 마지막 인덱스
  // 시작점과 끝점이 같아지면 더 이상 검색할 값이 없다는 의미
  while (start <= end) { 
    // 중간점은 변경되는 시작점 과 끝점을 기준으로 잡아야 함께 변경됨
    let mid = parseInt((start + end) / 2); 
    // 정렬된 배열의 시작값은 중간점에서 +-1 범위에 있다는게 정해져 있는듯 함
    // 중간점을 기준으로 시작점과 비교해서 앞쪽, 또는 뒤쪽이 정렬되어 있는지를 유추할 수 있다
    if (target === rotated[mid]) return mid; // mid 일치하면 mid 리턴
    else if (rotated[start] < rotated[mid]) { // 왼쪽이 정렬되어 있는 상태
      if (target < rotated[mid] && target >= rotated[start]) {
        end = mid - 1; // 타겟이 왼쪽에 있으면 범위를 왼쪽으로 좁힘
      } else { // 오른쪽에 있으니 범위를 오른쪽으로 좁힘
        start = mid + 1;
      }
    }
    else {// 오른쪽이 정렬된 상태, (rotated[start] > rotated[mid])
      if (target > rotated[mid] && target <= rotated[end]) {
        start = mid + 1; // 오른쪽에 있으니 범위를 오른쪽으로 좁힘
      } else {// 왼쪽에 있으니 범위를 왼쪽으로 좁힘
        end = mid - 1;
      }
    }
  }
  return -1; // 시작점과 끝점이 같아질 때까지 돌아도 안나오면 값이 없는 경우
};