[알고리즘] 이진 탐색 (Binary Search)

이진 탐색

• 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
• 배열 내부의 데이터가 정렬되어 있어야만 사용 가능함
• 변수 3개 (start, end, mid)를 사용해서 탐색함, 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정

이미지출처

과정

let output = binarySearch([0, 1, 2, 3, 4, 5, 6], 2);
console.log(output); // --> 2

1. 가운데 위치한 임의의 값 3을 선택한다.
2. 선택한 값 3과 찾고자 하는 값 2를 비교한다
3. 2<3이므로 2는 3의 좌측에 존제한다는 것을 알 수 있다.
4. [0, 1, 2]를 대상으로 다시 탐색을 진행한다.
5. 마찬가지로 가운데 임의의 값 1을 선택한다.
6. 1<2이므로 [2]를 남겨두고 또 다시 탐색을 진행한다.
7. 종료조건: 중간값이 찾는 값과 같을 경우까지 반복...
8. 반복의 범위: 남겨진 배열들이 계속 짧아지면서 start 시점이 end 시점보다 커질때까지
9. 반복문을 나왔을 때 리턴값을 찾지 못하면 찾는값이 배열에 없다는 것과 같으므로 -1리턴

코드

const binarySearch = function (arr, target) {
  
  let start = 0;
  let end = arr.length-1
  let mid
  
  while(start<=end){
  
  mid = parseInt((start+end)/2)
  
  if(target === arr[mid]){
    return mid;
  } else{
    if(target<arr[mid]){
      end = mid-1
    }
    else{
      start = mid+1
    }
  }
  }
  return -1

};