이진 검색 알고리즘

안녕하세요, #day_6입니다. 바이너리 검색 알고리즘에 대해 이야기하겠습니다.

이진 검색 알고리즘의 정의

반간 검색 또는 대수 검색이라고도 하는 이진 검색은 가장 유명한 검색 알고리즘 중 하나입니다.

this algorithm search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

• www.geeksforgeeks.org

공간 및 시간 복잡성

선형 탐색의 공간 복잡도는 O(1)이고 시간 복잡도는 O(log n)입니다.

파이썬에서 이진 검색 구현

def BinarySearchAlgorithm(wantedItem: int, sortedItems: list):
    """
    =>  Algorithm Name : Binary Search
    =>  Algorithm Type : Searching Algorithms
    =>  Time Complexity : O(n)
    =>  Space Complexity : O(1)
    =>  Logic
        [ if wantedItem == mid ]
        [ if wantedItem < sortedItems[mid] ] eliminate right half
        [ if wantedItem > sortedItems[mid] ] eliminate left half
    =>  Arguments
        [wantedItem]{int}
        [sortedItems] {list<int>} sorted list
    => Returns
        [index] if the wanted item exists in the list
        [False] if the wanted item doesn't exist in the list
    """
    low = 0
    high = len(sortedItems) - 1
    while low <= high :
        mid = (high + low) // 2
        if wantedItem == sortedItems[mid]:
            return mid
        elif wantedItem > sortedItems[mid]:
            # eliminate left half
            low = mid + 1
        else:
            # eliminate right half
            hight = mid - 1
    # if the item dosen't exist
    return False

자바스크립트에서 바이너리 검색 구현

/**
 * binary search algorithm
 * Time Complexity: O(log n)
 * Space Complexity: O(1)
 * @param wantedItem {Number} the desired element
 * @param sortedItems {Array<Number>} sorted array of numbers
 * @returns {(Number|Boolean)} (wantedItem) index if it exist otherwise (false)
 */
const BinarySearchAlgorithm = (wantedItem, sortedItems) => {
    let low = 0,
        high = items.length,
        mid;
    while (low <= high) {
        // the mid can be a float num that's why I used Math.floor
        mid = Math.floor((high + low) / 2);
        if (wantedItem == items[mid]) return mid;
        if (wantedItem < items[mid]) {
            // eliminate right half
            high = mid - 1;
        } else {
            // eliminate left half
            low = mid + 1;
        }
    }
    // if the wanted item dosen't exist
    return false;
};

시간 내주셔서 감사합니다! 좋은 하루 보내세요;
#day_6