(알고리즘)이진검색 이해하기

이진검색(Binary Search)란?

---

오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘

이진검색의 원리

1. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다.
2. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다.

이진검색의 특징

• 정렬된 리스트에만 사용할 수 있다.
• 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다.

이진검색의 시간 복잡도

O(logN)

이진검색을 사용하기 좋을때

• 오름차순으로 정렬된 데이터

이진검색 코드 만들어보기

function binarySearch(arr, elem) {
  var start = 0; //시작점
  var end = arr.length - 1; //끝점
  var middle = Math.floor((start + end) / 2); //중간점
  while (arr[middle] !== elem && start <= end) {
    //중간점이 elem이 다르고 시작점이 끝점보다 작거나 같을때 루프 실행
    if (elem < arr[middle]) {
      //elem이 중간점의 값보다 작을때
      end = middle - 1; //끝점을 중간점보다 한칸앞으로 당김, 오른쪽 범위 생략으로 축소
    } else {
      start = middle + 1; //시작점을 중간점보다 한칸뒤로 당김, 왼쪽 범위 생략으로 축소
    }
    middle = Math.floor((start + end) / 2); //시작점 또는 끝점이 옮겨진 후 중간점 다시 잡기
  }
  if (arr[middle] === elem) {
    console.log(middle);
  } else {
    console.log(-1);
  }
}

binarySearch([2, 5, 6, 9, 13, 15, 28, 30], 28);

결과값 6

시작, 중간, 끝점을 변수로 선언한 뒤 중간점이 찾고자 하는 값과 다르고 시작점이 끝점보다 작거나 같을때 루프를 실행한다.
실행된 루프에서 찾고자 하는 값이 중간점보다 작을때 끝점을 중간점보다 한 칸 앞으로 당겨 오른쪽 범위를 생략하여 축소시킨다.
찾고자하는 값이 중간점보다 클때 반대로 시작점을 중간점보다 한 칸 앞으로 당겨 왼쪽 범위를 생략하여 축소시킨다.
시작점이나 끝점이 옮겨졌다면 중간점을 다시 계산해서 잡는다.
찾고자 하는 값이 찾아질때까지 반복한다. 이때 찾고자 하는 값이 없다면 -1을 반환하고 찾는다면 중간값을 반환한다.