Binary search algorithm

Hi, this is #day_6, we’re going to talk about Binary Search Algorithm.

Definition of the binary search algorithm

binary search also called half-interval search, or logarithmic search is one of the most famous search algorithms,

this algo…

Hi, this is #day_6, we’re going to talk about Binary Search Algorithm.



Definition of the binary search algorithm

binary search also called half-interval search, or logarithmic search is one of the most famous search algorithms,

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.



Space and Time complexity

The space complexity of linear search is O(1) and his Time complexity is O(log n).



Implementation of binary search in python

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



Implementation of binary search in javascript

/**
 * 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;
};

Thank you so much for your time! Have a good day;
#day_6


Print Share Comment Cite Upload Translate
APA
Aya Bouchiha | Sciencx (2024-03-29T08:08:56+00:00) » Binary search algorithm. Retrieved from https://www.scien.cx/2021/06/18/binary-search-algorithm/.
MLA
" » Binary search algorithm." Aya Bouchiha | Sciencx - Friday June 18, 2021, https://www.scien.cx/2021/06/18/binary-search-algorithm/
HARVARD
Aya Bouchiha | Sciencx Friday June 18, 2021 » Binary search algorithm., viewed 2024-03-29T08:08:56+00:00,<https://www.scien.cx/2021/06/18/binary-search-algorithm/>
VANCOUVER
Aya Bouchiha | Sciencx - » Binary search algorithm. [Internet]. [Accessed 2024-03-29T08:08:56+00:00]. Available from: https://www.scien.cx/2021/06/18/binary-search-algorithm/
CHICAGO
" » Binary search algorithm." Aya Bouchiha | Sciencx - Accessed 2024-03-29T08:08:56+00:00. https://www.scien.cx/2021/06/18/binary-search-algorithm/
IEEE
" » Binary search algorithm." Aya Bouchiha | Sciencx [Online]. Available: https://www.scien.cx/2021/06/18/binary-search-algorithm/. [Accessed: 2024-03-29T08:08:56+00:00]
rf:citation
» Binary search algorithm | Aya Bouchiha | Sciencx | https://www.scien.cx/2021/06/18/binary-search-algorithm/ | 2024-03-29T08:08:56+00:00
https://github.com/addpipe/simple-recorderjs-demo