이진 탐색 (Binary Search)

이진 탐색

이진 탐색 알고리즘은 정렬된 데이터에서 범위를 줄여가면서 데이터를 탐색하는 방법입니다. 중요한 것은 정렬되어 있는 데이터에서만 사용할 수 있는 알고리즘 이라는 것입니다.

 

이진 탐색의 과정은 다음과 같습니다.

1. start, end로 mid 값을 설정합니다.
2. mid 값과 찾고자 하는 값과 비교합니다.
3. 찾고자 하는 값이 mid 보다 높으면 start = mid + 1,
   찾고자 하는 값이 mid 보다 낮으면 end = mid - 1
4. 값을 찾거나 start 위치가 end를 넘어설때까지 반복합니다.

 

11을 찾는 아주아주 간단한 예를 보겠습니다.

1

3

5

7

9

11

13

  start                        mid                        end

-> 11 > mid  이므로, start의 위치를 9로 옮김

1

3

5

7

9

11

13

                                         start    mid     end

-> 11 = mid 이므로, 종료

 

자바스크립트 코드

function binarySearch(arr, target){
  let startIdx = 0;
  let endIdx = arr.length - 1;
  
  while(startIdx <= endIdx){
    let midIdx = Math.floor((startIdx + endIdx) / 2);
    
    if(arr[midIdx] === target){
      return midIdx;
    }
    else if(arr[midIdx] < target){
      startIdex = midIdx + 1;
    }
    else if(arr[midIdx] > target){
      endIdx = midIdx - 1;
    }
  }
  
  return -1;
}

let nums = [10, 20, 30, 40, 50, 60]; 
console.log(binarySearch(nums, 30));

 

이진 탐색 알고리즘은 mid와 비교해서 절반씩 범위를 줄여나가며 데이터를 찾는 알고리즘입니다. 내용에서 특별히 어려운 부분은 없으니 공부하시면 좋을 것 같습니다. : >