🌊 [javascript] 이진탐색

🌊 이진 탐색

🐤 문제 설명

부분적으로 오름차순 정렬*된 정수의 배열(rotated)과 정수(target)를 입력받아 target의 인덱스를 리턴해야 합니다.

• 부분적으로 정렬된 배열: 배열을 왼쪽 혹은 오른쪽으로 0칸 이상 순환 이동할 경우 완전히 정렬되는 배열
• 예시: [4, 5, 6, 0, 1, 2, 3]은 왼쪽으로 3칸 또는 오른쪽으로 4칸 순환 이동할 경우 완전히 정렬됩니다.

 

🐣 제한사항

• rotated에 중복된 요소는 없습니다.
• target이 없는 경우, -1을 리턴해야 합니다.
  
  

🐥 입출력 예

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

 

🐋 입출력 예 설명

입출력 예 #1 rotated

• number 타입을 요소로 갖는 배열
• rotate[i]는 정수

입출력 예 #2 target

• number 타입의 정수

🐳 나의 풀이

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

  while (start <= end) {
    //점점 좁혀지다가 start와 end의 순서가 어긋나게 되면 반복을 종료한다

    mid = parseInt((start + end) / 2);

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

      //rotated는 나뉘어 정렬되어있으므로 분기점을 나눈다.
    if (rotated[start] < rotated[mid]) {
      // 왼쪽 절반이 정렬되어 있는 상태
      if (target < rotated[mid] && rotated[start] <= target) {
        // target이 중앙값보다 작고 시작값보다 크면 
        // 끝에 값을 mid보다 -1 해준다. 
        // 즉 범위를 절반으로 줄여버린다. 1~9가 범위고 target이 5보다 작다면
        // end를 9가 아닌 4로 잡아도 되기 때문
        end = mid - 1;
      } else {
        // 아니라면 start값을 mid+1로 해준다
        // 예를 들어 1~9가 범위고 target이 5보다 크다면 우리는 이제 6~9만 찾아보며 된다.
        start = mid + 1;
      }
    } else {
      // 오른쪽 절반이 정렬되어 있는 상태
      if (target <= rotated[end] && rotated[mid] < target) {
        //예를 들어 target이 9보다 작고 5보다 크다면
        // start값을 mid+1로 올려주고
        start = mid + 1;
      } else {
        // 아니라면 end값을 mid-1해준다.
        end = mid - 1;
      }
    }
   
  }
   return -1;
};

 

 

🦄 알아보기

이진 탐색은 데이터가 정렬되어있는 배열에서 특정한 값을 찾아내는 알고리즘으로, 배열의 중간에 있는 임의의 값을 찾고자 하는 값과 비교하여 임의의 값보다 작으면 임의의 값 이하의 값, 높으면 이상의 값을 탐색하는 것을 해당 값을 찾을 때 까지 반복한다.

해당 문제는 부분적인 정렬이기 때문에 분기처리를 따로 해줘야 풀리는 문제였다. 시간복잡도를 고려할 때 유용한 알고리즘 풀이법인 것 같다.