💁‍ 이진탐색

const list = ['a', 'b', 'c', 'd', ...]

🤷‍ 탐색?

• 이러한 배열이 있을때, 원하는 값을 찾는 문제를 탐색문제
• 'a' 부터 하나씩 찾는 방법을 단순 탐색(simple search)
• 배열의 중간부터 찾기 시작하는 방법 이진 탐색(binary search)
  • 이진 탐색 알고리즘은 리스트에 원하는 원소가 있다면 그 원소의 위치를 반환
  • 그렇지 않을때에는 -1 이나 null 과 같은 값을 반환

예제 🔎

function binarySearch(list, item){
  // low 와 high 는 탐색해야하는 범위
  let low = 0
  let high = list.length - 1

  while (low <= high) { // 탐색해야 하는 범위 제한
    let mid = parseInt((low + high)/2) // 중간
    let guess = list[mid]
    if(guess === item){
      return mid
    } 
    if(guess > item){
      high = mid - 1
    } else {
      low = mid + 1 
    }
  }

const myList = [1, 3, 5, 7, 9]

console.log(binarySearch(myList, 7)) // 3
console.log(binarySearch(myList, -1)) // -1

🙆‍ 뭐가 좋은건데?

• 시간 절약 -> 즉 비용이 절약 된다.
  • 단순 탐색 방법을 이용하면 처음부터 찾는 item 까지 계속해서 확인해야한다. 즉 추측해야 할 최대 횟수는 리스트의 길이와 같다.(이런것을 선형시간(linear time) 이라고 한다.)
  • 하지만 이진 탐색은 리스트에 8개가 있다면 최대 3번만 확인해도 된다. (로그시간(logarithmic time))

hello coding 그림으로 개념을 이해하는 알고리즘 을 참고하여 작성하였습니다.