[알고리즘 위한 한발짝 두발짝🐾] 이진탐색

<본 블로그는 코딩문 codingmoon 님의 유튜브를 참고해서 공부하며 작성하였습니다 :-)>

=> 개발자 필수 알고리즘 #3. 이진탐색 쉽고 간단하게

 

🫧 이진탐색

: 분할 정복 패턴을 지향하는 탐색 알고리즘

: 인풋 배열/데이터가 정렬되어 있는 조건하에 적용됨

 

🫧 이진탐색 vs 선형탐색

이진탐색	선형탐색
worst : O(log n) 매회 자료를 반으로 나눠가며 탐색 (선형보다 빠름)	worst : O(n) 순차적인 탐색 패턴
인풋 데이터 정렬 분할 정복 유형	작거나 중간 사이즈의 데이터셋에 적절

 

🫧 이진탐색 원리

1) L, M,  (중간 지점), R 포인트 준비

2) 배열의 M 수가 찾는 숫자와 같다면 M 리턴

추측 숫자가 찾는 숫자보다 작다면 L을 M + 1 위치로 이동 (좌측 숫자들 탐색에서 제외)

추측 숫자가 찾는 숫자보다 크다면 R을 M - 1 위치로 이동 (우측 숫자들 탐색에서 제외)

3) 반복

const num = [1, 5, 13, 17, 32, 39, 45, 50]

function binarySearch(arr: number[], target: number) {
	let left = 0;
    let right = arr.length - 1;
    
    while (left <= right) {
    	let middle = Math.floor((left - right) / 2)
        
        if (arr[middle] === target) {
        	// found!
            return middle
        } else if (arr[middle] < target) {
        	left = middle + 1
        } else if (arr[middle] > target) {
        	right = middle - 1
        }
    }
    return -1;
}

binarySearch(nums, 45)	// 6
binarySearch(nums, 55)	// -1