[알고리즘] 이진탐색(binary search) 기본개념 + js코드

이진탐색

 

 

240,000 개의 값이 있을때

단순탐색은 최대 240,000번 추측해야하지만,

이진탐색은 최대 18번의 추측으로 정답을 찾아낼 수 있다.

 

크기가 커질수록 단순탐색과는 비교도 안될정도의 빠른속도로 정답을 찾아낼 수 있다.

단, 이진탐색은 원소들이 정렬되어 있어야만 사용할 수 있다.

 

 

 

javascript로 구현한 이진탐색

function binarySearch (target, dataArray) {
    let low = 0;
    let high = dataArray.length - 1;
    
    while (low <= high) { // 탐색범위가 하나가 될때까지 루프를 실행시킨다.
        let mid = Math.floor((low + high) / 2); // js는 low+high가 홀수일 경우 정수로 내림합니다!
        let guess = dataArray[mid];
        
        if (guess === target) { // 추측값이 정답일 경우
        	return guess;
        } else if (guess > target) { // 추측값이 정답보다 클 경우
        	high = mid - 1;
        } else { // 추측값이 정답보다 작을 경우
        	low = mid + 1;
        }
    }
    return undefined;
}

 

 

 

---

 

 

단순탐색과 이진탐색 옆에 써있는 저것은? 빅오표기법 ㅎㅎ!

 

https://pro-jm.tistory.com/56

[빅오표기법] 빅오표기법이란? (Big O notation)