[알고리즘/javascript] 이진탐색 & 변형된 이진탐색

이진탐색 알고리즘

개념

이미 정렬되어 있는 배열에서 탐색 범위를 두 부분으로 나눠 절반씩 좁혀가 필요한 부분에서만 탐색하도록 제한하여 원하는 값을 찾는 알고리즘이다.

 

 

이진 탐색은 알고리즘은 left, right, mid 이 세 개의 변수가 필요하다.

 

left은 왼쪽의 끝 인덱스를 뜻하며 right는 오른쪽의 끝 인덱스를 뜻하고 left와 right의 사이는 탐색범위가 된다.

mid는 left와 right 범위의 중간점을 뜻하며 탐색하는 범위에서의 중간점이다.

이때 중간점은 (left + right) / 2 란 공식으로 구할 수 있다.

 

이진 탐색의 시간 복잡도는 O(logN)이며 단순히 매번 절반의 탐색할 데이터를 제외시킨다 생각하면 된다.

탐색범위의 중간 인덱스를 지정하고, 찾고자 하는 값(target)과 현재 중간 값을 비교한다.

 

이때 target 값과 중간 값의 비교 값에 따른 조건을 걸어준다.

• 중간 값보다 target 값이 크다면 중간 값보다 작은 수는 더 이상 범위에 해당하지 않기에 left의 값은 mid + 1이 된다.
• 중간 값보다 target 값이 작다면 중간 값보다 큰 수는 더 이상 범위에 해당하지 않기에 right의 값은 mid - 1이 된다.

 

이를 반복하며 만약에 target 값과 중간 값이 일치하면 해당 mid의 위치에 찾는 값이 존재하므로 해당 값을 반환해주고, left와 right의 값이 mid의 값과 같음에도 중간 값이 일치하지 않으면 배열에 찾는 값이 존재하지 않으므로 -1을 반환해준다.

 

코드

const binarySearch = (list, target, left, right) => {
  let mid = 0;

  while (left <= right) {
    // 가운데 인덱스
    mid = Math.floor((left + right) / 2);

    if (list[mid] === target) {
      return mid;
    }
    
    // 대소 비교로 범위 지정
    if (list[mid] > target) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }

  return -1;
}

const sample = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

sample.sort((a, b) => a - b);

// ( 찾을 배열, 탐색할 값, 시작점, 끝점 )
const result = binarySearch(sample, 7, 0, sample.length - 1);

console.log(result);

참고한 블로그)

https://gurtn.tistory.com/94

[JS] 이진 탐색(이분 탐색)

---

이진탐색 알고리즘 변형 문제

문제

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

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

입력

인자 1 : rotated

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

인자 2 : target

• number 타입의 정수

출력

• number 타입을 리턴해야 합니다.

주의사항

• 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

 

코드

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

  while (left <= right) {
    let middle = parseInt((right + left) / 2);

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

    if (rotated[left] < rotated[middle]) {
      // 왼쪽 절반이 정렬되어 있는 상태
      if (target < rotated[middle] && rotated[left] <= target) {
        right = middle - 1;
      } else {
        left = middle + 1;
      }
    } else {
      // 오른쪽 절반이 정렬되어 있는 상태
      if (target <= rotated[right] && rotated[middle] < target) {
        left = middle + 1;
      } else {
        right = middle - 1;
      }
    }
  }

  return -1;
};

 

예시 1

rotated => [10,11,0,1,2] target => 11

1. left 값은 10, middle 값은 0, right  값은 2가 된다.
2. left 값이 middle 값보다 크므로 오른쪽 절반이 정렬되어 있는 상태([0,1,2])에 해당하는 'else' 절로 넘어간다.
3. target이 right 값보다 크므로 right 인덱스는 middle -1 인 1이 되고, right 값은 11이 된다. 
4. left 값은 10, middle 값은 10, right값은 11이 된다. 
5. left값과 middle 값이 같으므로 else 절로 넘어간다.
6. target이 right 값과 같으므로 left 인덱스는 middle + 1인 1이되고, left 값은 11이 된다.
7. left 값, right 값 모두 11이고, middle값도 11이 되므로 11의 인덱스를 리턴한다.

 

예시 2

rotated => [10,11,12,0,1] target => 1

1. left 값은 10, middle 값은 12, right  값은 1이 된다.
2. left 값이 middle 값보다 작으므로 왼쪽 절반이 정렬되어 있는 상태([10,11,12])에 해당하는 'if' 절로 넘어간다.
3. target이 middle 값과 left 값보다 작으므로 left 인덱스는 middle + 1 인 3이 되고, left 값은 0이 된다. 
4. left 값은 0, middle 값은 0, right값은 1이 된다. 
5. left값과 middle 값이 같으므로 else 절로 넘어간다.
6. target이 right 값과 같으므로 left 인덱스는 middle + 1인 4가되고, left 값은 1이 된다.
7. left 값, right 값 모두 1이고, middle값도 1이 되므로 1의 인덱스를 리턴한다.

 

예시 3

rotated => [1,2,3] target => 3

1. left 값은 1, middle 값은 2, right  값은 3이 된다.
2. left 값이 middle 값보다 작으므로 왼쪽 절반이 정렬되어 있는 상태([1,2])에 해당하는 'if' 절로 넘어간다.
3. target이 middle 값보다 크므로 left 인덱스는 middle +1 인 1이 되고, left 값은 2이 된다.
4. left 값은 2, middle 값은 2, right값은 3이 된다. 
5. left 값과 middle 값이 같으므로 else 절로 넘어간다.
6. target이 right 값과 같으므로 left 인덱스는 middle + 1인 2가되고, left 값은3이 된다.
7. left 값, right 값 모두 3이고, middle값도 3이 되므로 3의 인덱스를 리턴한다.