JS로 binary search 구현하기

binary search란❓

• 이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘.

• 이진탐색(O(logN))은 단순한 배열 순회(O(N))보다 시간복잡도에서 크게 이점을 갖는다

순회 방법

1. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다.

2. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다.

3. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다.

4. 해당 값을 찾을 때까지 이 과정을 반복한다.

💡 binary search 구현

function MyBinarySearch(arr, target) {
    let startIdx = 0;
    let endIdx = arr.length - 1;
    let midIdx;

    while (startIdx <= endIdx) {
        midIdx = Math.floor((startIdx + endIdx) / 2);
        if (target === arr[midIdx]) {
            return midIdx;
        }

        if (target < arr[midIdx]) {
            endIdx = midIdx - 1;
        }
        else {
            startIdx = midIdx + 1;
        }
    }
    return -1;
}