[107일차]이진탐색 알고리즘

이진탐색 알고리즘

이진탐색은 간단히 구현할 수 있으면서도,
배열을 전부 순회 하지않고 원하는 값을 찾을 수 있는 강력한 알고리즘이다.
검색원리상, 정렬된 배열에서만 찾을 수 있지만, 찾는 속도가 매우 빠르다

원리

밑 그림과 같이 오름차순으로 정렬된 배열이 있다.

아래 배열에서 찾는값은 21

처음 임의의 중간값을 고른다.

14는 21보다 작으므로 고른값의 오른쪽에 찾는값이 있다는걸 알 수 있다.
그러면 찾을 범위가 4번째인덱스부터 6번인덱스로 줄어든다! WOW!

이 찾을 범위에서 가운데 임의값을 꺼내서
찾는값과 비교한다.

단 두번의 검색으로 원하는 값을 찾았다!

원리를 알았으니 코드로 구현해보자.

자바스크립트 코드

const binarySearch = function (arr, target) {
  // 탐색함수 선언 찾을범위를 인자로 받는다.
    // 만약 찾을 범위의 가운데 값이 target과 같으면 가운데 인덱스 리턴
    // 만약 찾을 범위의 첫번째와 마지막인덱스가 같으면 -1리턴
    // 찾을 범위의 첫번째와 마지막인덱스가 1차이 나면 (바로 옆)
      // 만약 mid + 1 값이 target과 같으면 mid + 1리턴
      // 그외엔 -1리턴
    
    //가운데 값이 target보다 크면 가운데값의 오른쪽범위를 인자로넣고 탐색
    //가운데 값이 target보다 작으면 가운데값의 왼쪽범위를 인자로 넣고 탐색
 
  function search (start, end){
    let mid = parseInt((start + end) / 2)
    if(arr[mid] === target)return mid;
    if(start === end)return -1;
    if(end - start === 1){
      if(arr[mid + 1] === target)return mid + 1;
      return -1;
    }
 
    if(arr[mid] < target)return search(mid + 1, end);
    if(arr[mid] > target)return search(start, mid - 1);
  }
  return search(0, arr.length - 1);
};