📚이진탐색 알고리즘

출처 사이트로 이동 : penjee.com

정렬된 배열에서 특정 값을 찾는 알고리즘으로 배열의 중간을 기준으로 데이터를 탐색하기 때문에
반드시 데이터가 정렬된 상태로 존재해야 탐색을 할 수 있습니다

중간을 기준으로 탐색 대상을 절반씩 줄여가는 탐색 알고리즘으로 O(logN) 시간복잡도를 가집니다

코드

arr에서 target의 인덱스를 반환하는 코드입니다

const binarySearch = function (arr, target) {
  const search = function (start, end) {
    let mid = parseInt((start + end) / 2);

    if (start === end) {
      return arr[mid] === target ? mid : -1;
    }

    if (target > arr[mid]){
      return search(mid + 1, end);
    } else if (target =< arr[mid]) {
      return search(0, mid);
    } 
    }   
  }
  return search(0, arr.length - 1);
};

해설

1. let mid = pasrseInt((start + end) / 2);
변수 mid에 첫번째 인덱스와 마지막 인덱스의 중간 인덱스를 할당

2. 재귀탈출 조건
재귀를 통해 계속해서 배열의 길이 / 2 첫번째 인덱스와 마지막 인덱스가 같아질때
즉, arr.length가 1이 될 때 arr[start] === target 을 만족할 경우 start반환 아닐 경우 -1 반환

if (start === end) {
      return arr[start] === target ? start : -1;
    }

3. target과 arr[mid] 비교

• target > arr[mid]
arr의 start = mid + 1, end = end 로 다시 search 함수의 인자로 들어갑니다

• target <= arr[mid]
arr의 start = 0, end = mid 로 다시 search 함수의 인자로 들어갑니다

4. return search(0, arr.length -1);
arr의 0번째 인덱스와 마지막 인덱스를 인자로 받는 함수를 리턴하도록 합니다

➡️ 탈출조건을 만족할 때 까지 search(start, end)함수를 재귀로 반복합니다.