Binary Search Tree를 이용한 검색값 찾기

알고리즘 눈덩이⛄️

🧑‍🏫 문제

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

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

🧐 What is Binary Search Tree?

(이진탐색트리란 무엇인가?)

정렬이 되어있고, 고유한 정수로만 이루어진 배열이 있다
이 배열로 이진검색트리를 구현하시오

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 가 있고 내가 특정 숫자를 검색하고자 한다면
배열에서 가운데 숫자를 가져온 다음
1. 가운데 숫자 < 검색하고자 하는 숫자 => 오른쪽의 데이터만 본다(왼쪽 데이터는 안봐도 상관없음) => 오른쪽의 데이터에서 다시 중간값을 찾는다 => 반복
2. 가운데 숫자 > 검색하고자 하는 숫자 => 왼쪽의 데이터만 본다(오른쪽 데이터는 안봐도 상관없음) => 왼쪽의 데이터에서 다시 중간값을 찾는다 => 반복
3. 가운데 숫자 = 검색하고자 하는 숫자 => 찾았음
이런 식으로 찾아들어가면 된다.

만약 중간값이 4라고 하고(중간값이 딱 떨어지지 않을 때는 앞에 있는 녀석을 중간값으로 생각하기로 하자) 2를 찾는다고 생각해보면 배열은
[0, 1, 2, 3]를 들고온다 그리고 다시 1이 중간값이라고 생각하면 배열은
[2, 3]을 들고온다 그리고 다시 2가 중간값이라고 생각하면 우리가 원하는 값을 찾았다

여기 동영상을 참고

🖋️ Pseudocode (수도코드)

1. 배열의 왼쪽 끝 인덱스 값과 오른쪽 끝 인덱스 값을 들고온다
2. 중간값이 우리가 찾고자하는 검색값이면 해당 값을 리턴한다.
3. 우리는 부분적으로 오름차순 정렬된 배열을 들고 있음으로 중간값 기준으로 어느쪽이 오름차순으로 정렬되어있는지 분기를 나눠 처리해준다
   3-1. 중간값기준 배열의 왼쪽이 오름차순으로 정렬되어 있는 상태
   3-1-1. 만약 배열의 왼쪽에 우리가 찾는 타겟값이 있다면 right의 index를 middle - 1로 해줌으로써 왼쪽 배열만 가져옴
   3-1-2. 만약 배열의 왼쪽에 우리가 찾는 타겟값이 있다면 left의 index를 middle + 1로 해줌으로써 오른쪽 배열만 가져옴
   3-2. 중간값기준 배열의 오른쪽이 오름차순으로 정렬되어 있는 상태
   3-2-1. 만약 배열의 오른쪽에 우리가 찾는 타겟값이 있다면 left의 index를 middle + 1로 해줌으로써 오른쪽 배열만 가져옴
   3-2-2. 만약 배열의 오른쪽에 우리가 찾는 타겟값이 있다면 right의 index를 middle - 1로 해줌으로써 왼쪽 배열만 가져옴
4. 2번이 도출될 때까지 위의 과정을 반복

👾 Code

const rotatedArraySearch = function (rotated, target) {
    // TODO : 여기에 코드를 작성합니다.
  
    //   for (let i = 0; i < rotated.length; i++) {
    //     if (rotated[i] === target) {
    //       return i;
    //     }
    //   }
    //   return -1;
    
    let left = 0;
    let right = rotated.length - 1;
  
    while (left <= right) {

      let middle = parseInt((right + left) / 2); //중간값을 구한다
      
      //<2. 중간값이 우리가 찾는 검색값이면 값을 찾았음으로 그 값을 return한다>
      if (rotated[middle] === target) {
        return middle;
      }
      
      if (rotated[left] < rotated[middle]) {
        // <3-1. 중간값기준 배열의 왼쪽이 오름차순으로 정렬되어 있는 상태>
        if (target < rotated[middle] && rotated[left] <= target) { //만약 배열의 왼쪽에 우리가 찾는 타겟값이 있다면
          right = middle - 1; //right의 index를 middle - 1로 해줌으로써 왼쪽 배열만 가져옴
        } else { //만약 배열의 왼쪽에 우리가 찾는 타겟값이 없다면
          left = middle + 1; //left의 index를 middle + 1로 해줌으로써 오른쪽 배열만 가져옴
        }
      } else {
        // <3-2. 중간값기준 배열의 오른쪽이 오름차순으로 정렬되어 있는 상태>
        if (target <= rotated[right] && rotated[middle] < target) { //만약 배열의 오른쪽에 우리가 찾는 타겟값이 있다면
          left = middle + 1; //left의 index를 middle + 1로 해줌으로써 오른쪽 배열만 가져옴
        } else { //만약 배열의 오른쪽에 우리가 찾는 타겟값이 없다면
          right = middle - 1;//right의 index를 middle - 1로 해줌으로써 왼쪽 배열만 가져옴
        }
      }

    }
  
    return -1; //배열에 찾고자하는 타겟 값이 존재하지 않는다면 -1을 return한다.  
  };


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

😵
알고리즘.. 진짜 밀려있다.. 눈덩이처럼 커져간다..
막상하면 재밌는데..
시작하기가 너무 괴롭다..