그 인덱스에 있는 값

문제 설명

배열과 숫자 하나를 전달받는 search 함수는 해당 숫자의 인덱스에 해당하는 값을 반환한다. 전달받은 숫자에 해당하는 인덱스에 값이 존재하지 않을 경우 -1을 반환한다. 전달받은 배열은 정렬되어 있다.

입력 예시는 다음과 같다

search([1, 2, 3, 4, 5, 6], 4) // 3
search([1, 2, 3, 4, 5, 6], 6) // 5
search([1, 2, 3, 4, 5, 6], 11) // -1

이 문제를 일반적으로 배열에 대해 루프를 전체적으로 한번씩 돌아, 배열이 처음부터 끝까지 돌며 해당 숫자를 찾는 방식은 시간복잡도가 O(n)을 가지게 된다.
즉 전체 배열을 한번 훑어보고 찾거나 못 찾거나 둘 중 하나이다.

이에 대한 단순한 해결책은 다음과 같다.

function search(arr, val) {
  for (let i = 0; i < arr.length; i++) {
   if (arr[i] === val) {
    return i; 
   }
  }
  return -1;
};

하나의 루프를 가지고 O(n)의 시간 복잡도를 가진다. 이러한 구졸르 선형 탐색이라고 한다.

우리가 이번에 살펴보고자 하는 것은 약간 다르다. 이진 탐색을 이용하여 문제를 풀어볼 것인데, 이는 분할과 정복 알고리즘을 이용하는 방법이다.

소스 코드는 다음과 같다.

function search(array, val) {
 let min = 0;
 let max = array.length - 1;
  
 while (min <= max) {
    // 배열의 중간값을 취한다.
 	let middle = Math.floor((min + max) / 2);
    let currentElement = array[middle];
   
    // middle을 val과 비교하며 최신화한다. 
    // 효율적인 탐색을 위해 값이 존재하지 않을 부분은 바로 무시하는 방식을 취한다.
   	if (array[middle] < val) {
      min = middel + 1;
    }
    else if (array[middle] > val) {
      max = middle - 1; 
    }
    else {
      // middle의 값이 val과 같다면 리턴한다.
      return middle;
    }
 }
 // val에 해당하는 값이 없다면 -1을 리턴한다.
 return -1;
};

위와 같이 분할 정복 알고리즘으로 시간을 절약할 수 있다. 위 소스 코드의 시간복잡도는 Ologn 이다.