TIL-2024.03.07 - 알고리즘 - 이진 탐색(Binary Search) 알고리즘

------- 이진 탐색(Binary Search) 알고리즘

설명:

• 이진 탐색은 정렬된 배열에서 특정 요소를 찾는 알고리즘.
• 배열을 반으로 나누어 탐색 범위를 반으로 줄여나가는 방식으로 동작.
• 이 알고리즘은 탐색 범위를 반으로 줄이기 때문에 일반적으로 선형 탐색보다 효율적으로 동작.

 

동작 방식: 

1. 시작, 중간, 끝 지점 설정: 배열의 시작 지점을 start, 중간 지점을 mid, 끝 지점을 end로 설정합니다.
2. 중간 요소 검사: 배열의 중간 요소를 확인하여 찾고자 하는 값과 비교합니다.
3. 탐색 범위 축소: 중간 값이 찾고자 하는 값보다 작으면 시작 지점을 중간 지점 다음으로 설정하고, 크면 끝 지점을 중간 지점 이전으로 설정합니다.
4. 반복: 찾고자 하는 값이 발견될 때까지 위의 과정을 반복합니다.

 

예제:

 

function binarySearch(arr, target) {
    let start = 0;
    let end = arr.length - 1;

    while (start <= end) {
        let mid = Math.floor((start + end) / 2);

        if (arr[mid] === target) {
            return mid; // 찾고자 하는 값의 인덱스를 반환합니다.
        } else if (arr[mid] < target) {
            start = mid + 1; // 중간 값보다 크면 시작 지점을 중간 지점 다음으로 이동합니다.
        } else {
            end = mid - 1; // 중간 값보다 작으면 끝 지점을 중간 지점 이전으로 이동합니다.
        }
    }

    return -1; // 찾고자 하는 값이 배열에 없을 경우 -1을 반환합니다.
}

// 예제
const arr = [1, 3, 5, 7, 9, 11, 13, 15];
const target = 9;
const index = binarySearch(arr, target);
console.log("찾고자 하는 값의 인덱스:", index);