이진 탐색 Binary Search

탐색은 배열 형태로 주어진 데이터에서 원하는 값을 가진 데이터를 찾는 문제이다. 

이진 탐색은 탐색의 대상이 되는 데이터가 정렬된 상태로 주어진 경우에 효과적으로 탐색을 수행할 수 있다. 

 

배열에서 탐색키 X를 찾는 과정은 다음과 같다. 

 

정렬된 배열에서 가운데 있는 원소와 탐색키 X를 비교하여 두 값이 같으면 원하는 키를 찾았으므로 탐색을 종료한다. 

그렇지 않으면 배열은 가운데 원소를 기준으로 왼쪽과 ㄷ오른쪽의 두 개의 부분배열로 분할되는데, 만약 X가 가운데 원소보다 작으면 왼쪽 부분배열을 사용해서 이진 탐색을 다시 수행하고, X가 가운데 원소보다 크면 오른쪽 부분배열을 사용해서 이진탐색을 다시 수행한다. 

 

이러한 과정을 순환적으로 수행하면 배열에서 X를 찾거나 이진 탐색의 대상이 되는 부분배열이 빈 배열이 되어 X가 존재하지 않는다는 것을 알 수 있다. 

 

이진 탐색 알고리즘을 분할정복 방법의 세 단계에 대응시켜 보면 다음과 같다. 

 

- 분할 : 배열을 가운데 원소를 기준으로 왼쪽 부분 배열과 오른쪽 부분 배열로 분할한다. 탐색키 X가 가운데 원소와 같으면 가운데 원소에 해당하는 배열의 인덱스를 반환하고 종료한다. 

- 정복 : X가 가운데 원소보다 작으면 왼쪽 부분배열을 대상으로 이직 탐색을 순환호출하고, 크면 오른쪽 부분배열을 대상으로 이진 탐색을 순환호출한다. 탐색을 다시 수행할 때마다 탐색 범위가 절반으로 줄어든다. 

- 결합 : 부분배열에 대해서 이진 탐색의 결과가 직접 반환되므로 결과를 결합할 필요가 없다. 

 

1. 반복 호출 

const binarySearch = (nums, target) => {
  let result = 0;
  let startIndex = 0; 
  let endIndex = nums.length - 1; 
  
  while ( startIndex <= endIndex ) {
    let mid = Math.floor((startIndex + endIndex) / 2);
    if ( nums[mid] === target ) {
      result = mid; 
      break;
    } else if ( nums[mid] < target ) {
      startIndex = mid + 1; 
    } else {
      endIndex = mid - 1; 
    }
  }
  
  return result;
}

 

2. 순환 호출

const binarySearch => (nums, startIndex, endIndex, target) => {
  if ( startIndex >= endIndex ) return; 
  
  const mid = Math.floor((startIndex + endIndex)/2); 
  
  if ( target === nums[mid] ) {
    return mid; 
  } else if ( target > nums[mid] ) {
    binarySearch(nums, mid+1, endIndex, target);
  } else {
    binarySearch(nums, startIndex, mid-1, target);
  } 
}