자바스크립트에서 이진탐색 알고리즘

• 이미 정렬된 배열에서 값을 찾아내기 위한 방법으로 이진탐색 알고리즘에 대해서 정리하고자 한다.
• 단순히 for문으로 배열의 값을 찾고자 한다면, O(N)의 시간복잡도가 걸릴 것이다.
• 이 보다 빠른 탐색 알고리즘으로, O(logN)의 시간복잡도를 가지는 알고리즘이 이진탐색 알고리즘이다.

const binarySearch = (sortedArray, targetNum) => {
	let targetIndex = -1;
    let left = 0;
    let right = sortedArray.length - 1;
    
    while(right > left) {
    	const mid = Math.floor((left + right) / 2); // 가운데 값
        if(sortedArray[mid] === targetNum) {
        	targetIndex = mid;
            break;
        } else if (sortedArray[mid] < targetNum) {
        	// mid를 기준으로 오른쪽을 탐색한다.
            left = mid + 1;
        } else {
        	// mid를 기준으로 왼쪽을 탐색한다.
            right = mid - 1;
        }
    }
    
    if(right === left && sortedArray[left] === targetNum) {
    	// 마지막 원소
        targetIndex = left;
    }
    
    return targetIndex;
}

• 가운데 원소를 기준으로 한 번에 절반씩 경우의 수를 줄여나간다.

• 마지막까지 위치를 찾지 못할 경우는 이 배열에는 목표 값이 존재하지 않는 상태를 뜻한다.
  🥮 이때 -1을 리턴한다.

• 위에서는 반복문으로 구현했지만, 재귀를 통해서도 이진탐색 알고리즘을 구현할 수 있다.