책보고 이해한 알고리즘 - binarySearch

그림으로 개념을 이해하는 알고리즘 - 이진탐색

simpleSearch

단순탐색 알고리즘은 빅오 표기법 O(N)로 표현하며,
데이터의 개수만큼 탐색해야하기에 N번 진행하는 알고리즘을 말한다.
책에서는 상대가 생각한 1~100중 한가지 숫자를 추측할때 1부터 2, 3...
하나씩 오름차순으로 숫자를 추측하는것을 예시로 들었다.
만약 답이 99라면 답에 도달하기까지 99번 추측해야한다.

binarySearch

이진탐색 알고리즘은 빅오 표기법 O(LogN)로 표현하며,
한번 처리가 진행될때마다 검색해야하는 데이터의 양이 절반씩 줄어드는 알고리즘을 말한다.
앞서 적은 예시에서 출발이 달라진다.
바로 100의 중간 50부터 시작한다.
그에 대한 대답이 너무 작다이면 50 이하의 숫자는 답이 아니라는것을 알 수 있다.
이렇게 중간 중간 중간으로 범위를 좁히면 숫자를 추측할때마다 처리해야할 데이터 양이 절반 줄어드는것이다.

binarySearch를 구현한 코드

const binarySearch = function (arr, target) {
  let left = 0; // 왼쪽 인덱스 (작은쪽)
  let right = arr.length-1 // 오른쪽 인덱스 (큰쪽)

  while (left <= right){ // left가 right가 겹치지 않을때까지 반복
    // binarySearch는 가운데에서부터 작으면 가운데 기준으로 왼쪽 크면 오른쪽으로 잘라 향하기때문에 가운데를 지정 
    const middle = parseInt((left + right)/2) 

    if (arr[middle] < target){
      // 가운데가 타겟보다 작을경우는 오른쪽으로 향해야하기 때문에 왼쪽을 가운데 다음 인덱스로 지정
      left = middle+1;
    }else if (arr[middle] > target){
      // 가운데가 타겟보다 클경우는 왼쪽으로 향해야하기 때문에 오른쪽을 가운데 전 인덱스로 지정
      right = middle-1;
    }else if (arr[middle] === target){
      // 가운데에서 찾았을경우
      return middle;
    }
  }
  //여기까지 왔다는건 left와 right가 겹쳤다는것이고 arr에는 찾고자하는 타겟이 없음!
return -1

};