[알고리즘] 이진 탐색

부분적으로 오름차순 정렬이 된 정수의 배열 rotated와 정수 target
두 인자를 입력 받아 rotated 내 target의 인덱스를 리턴하는 문제
만약 target이 존재하지 않으면 -1을 반환한다.

부분적으로 정렬되었다는 건 [0,1,2,3,4] 와 같은 형태가 아니라 [2,3,4,1,0] 과 같다고 생각하면 된다.

그냥 단순하게 생각하면 반복문을 돌려서 target을 찾아내면 그만이겠지만,
그런 경우는 시간 복잡도가 0(N)이라고 하고, 이진 탐색(binary search)을 이용하면 시간 복잡도가 O(logN)이라고 한다.

이진 탐색이라는 건 항상 주어진 수의 중앙에 있는 수를 확인해 찾는 수와 비교해 동일하면 해당 인덱스를,
그리고 동일하지 않을 경우에는 찾는 수보다 크면 그 수보다 작은 영역에서 탐색을 시작하고,
찾는 수보다 작을 경우에는 그 수보다 큰 영역을 탐색하며 점차 범위를 줄여나가는 방식이라고 보면 된다.

오름차순으로 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘이다. 리스트의 중간 부분에 찾는 원소가 있는지 확인하고, 없으면 위쪽에 있는지 아래쪽에 있는지 판단하여 맨 앞부터 검색하거나 중간부터 검색한다. (wiki)

내가 쓴 코드 (수도 코드)

//start와 end를 구할 때 math.max와 math.min을 이용해 각 인덱스를 저장
// mid는 start와 end의 중간값 인덱스 (start + end / 2)
// slice 써서 start부터 rotated.length-1 까지 자르고, 0번째부터 end까지 잘라서 정렬된 배열을 다시 만든 뒤 
// 정렬된 배열에서 이진 탐색 하고, 이진탐색으로 구한 target의 인덱스에 원 인덱스 값이 되도록 플러스 해준다 
// (start가 인덱스가 0이었다면 이미 정렬된 배열이므로 바로 이진 탐색)

이진 탐색을 좀 변형해서 풀어야 한다고 해서 나름대로 머리를 굴려보았으나...
딱 봐도 조잡한 방식을 사용하고 있음을 알 수 있다 ^^...

래퍼런스

const rotatedArraySearch = function (rotated, target) {
  let left = 0,
    right = rotated.length - 1;

  while (left <= right) {
    //left인덱스가 right인덱스보다 작거나 같은 동안 반복한다. 
    let middle = parseInt((right + left) / 2);

    if (rotated[middle] === target) {
      return middle;
    }
    
    //우선 온전히 정렬된 부분을 찾아본다 
    //항상 오른쪽 반이 정렬되어 있거나, 왼쪽 반이 정렬되어 있거나 
    //아니면 전체 배열이 오름차순으로 정렬되어 있는 세가지 경우만 존재함. 

    if (rotated[left] < rotated[middle]) {
      // 왼쪽 절반이 정렬되어 있는 상태
      //왜냐하면 가장 중앙값이 맨 왼쪽 끝 left 보다 크기 때문 
      //만약 그 사이에 정렬됨이 끝났다면 중앙값이 left보다 작을 것임.
      if (target < rotated[middle] && rotated[left] <= target) {
        //찾는 수가 middle인덱스 값보다 작고, left인덱스 값보다 크거나 같으면 
        //왼쪽 정렬된 내부에 있는 거니까 
        right = middle - 1;
        //right을 정렬된 왼쪽 안으로 가져오고 
      } else {
        //아닌 경우에느 왼쪽이 아닌 오른쪽 부분에 있는 거니까 
        //left를 오른쪽으로 옮겨서 그 안에서 찾는다. 
        left = middle + 1;
      }
    } else {
      // 오른쪽 절반이 정렬되어 있는 상태
      if (target <= rotated[right] && rotated[middle] < target) {
        left = middle + 1;
      } else {
        right = middle - 1;
      }
    }
  }

  return -1;
};