[JS][알고리즘] 이진 탐색(Binary Search Algorithm)

개념

이미 정렬된 배열에서 탐색 범위를 두 부분 리스트로 나눠 절반씩 좁혀서 가며 필요한 부분에서만 탐색하도록 제한하여 원하는 값을 찾는 알고리즘

 

특징 및 설명

오름차순으로 정렬된 배열이 필요하고 왼쪽의 끝 인덱스(left), 오른쪽 끝 인덱스(right), 중간 값(mid)이 필요함 -> 보통(start, end 사용)

 

target 값과 중간값 비교

1. target 값 == 중간 값이랑 같다 -> 끝!

2. target 값 < 중간 값 -> left = mid + 1 

3. target 값 > 중간 값 -> right= mid - 1 

 

복잡도

O(log(N))

매번 절반의 탐색할 데이터를 제외시킨다 라고 간단하게 생각하면 된다.

 

예시

배열 nums의 target 값은 9이고 배열의 중간 값(pivot)은 3

먼저, nums[pivot]은 3, 하지만 target 값인 9보다 작음 (3 < 9). left의 값은 pivot+1에 위치한 5가 된다.

다시 중간값을 구하게 되면 target = nums[pivot] 값이 같아서 탐색이 끝난다.

 

nums[pivot] > nums[left]
--> move right = pivot - 1 

nums[pivot] > nums[left]
--> move left = pivot + 1

nums[pivot] = target
--> return pivot = 4

 

 

문제 및 코드

https://leetcode.com/problems/binary-search/

function(nums, target) {
    let left = 0;
    let right = nums.length -1;

    
    while(left <= right){
        let mid = Math.floor(((left + right) / 2))
        if(nums[mid] == target) return mid;
        else if(nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    
    return -1
    
};