Scribd Logo
Upload

Welcome to Scribd!

  • 53 views

    Binary Search SDD

    Uploaded by

    d
    Binary search is more efficient than linear search but requires a sorted list. It divides the list at the middle, compares the target value, and ignores half the list. This process repeats, narrowing the search space until the target is found or determined absent. It is very efficient, reducing a list of 100,000 items to 12,500 after only 3 comparisons. The pseudocode sets upper and lower bounds, gets the middle value, and updates the bounds based on comparisons to efficiently find the target.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Binary Search SDD

    Uploaded by

    d
    53 views2 pages
    Binary search is more efficient than linear search but requires a sorted list. It divides the list at the middle, compares the target value, and ignores half the list. This process repeats, narrowing the search space until the target is found or determined absent. It is very efficient, reducing a list of 100,000 items to 12,500 after only 3 comparisons. The pseudocode sets upper and lower bounds, gets the middle value, and updates the bounds based on comparisons to efficiently find the target.

    Original Description:

    sdd hsc binary search

    Original Title

    Binary Search sdd

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Binary search is more efficient than linear search but requires a sorted list. It divides the list at the middle, compares the target value, and ignores half the list. This process repeats, narrowing the search space until the target is found or determined absent. It is very efficient, reducing a list of 100,000 items to 12,500 after only 3 comparisons. The pseudocode sets upper and lower bounds, gets the middle value, and updates the bounds based on comparisons to efficiently find the target.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    53 views2 pages

    Binary Search SDD

    Uploaded by

    d
    Binary search is more efficient than linear search but requires a sorted list. It divides the list at the middle, compares the target value, and ignores half the list. This process repeats, narrowing the search space until the target is found or determined absent. It is very efficient, reducing a list of 100,000 items to 12,500 after only 3 comparisons. The pseudocode sets upper and lower bounds, gets the middle value, and updates the bounds based on comparisons to efficiently find the target.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 2

    SEARCHING

    BINARY SEARCH

    A binary search is a more efficient method of searching a list than a linear search but, unlike
    a linear search, ​requires that a list be initially sorted​.

    The sorted array is divided at the middle index position and the target value is compared to
    the element in the middle position to determine if it is greater than, less than or equal to the
    element in the middle position. If it is equal, then we have found the target value. If the target value
    is less than the element in the middle position, then the target value is in the lower half of the array.
    If the target value is greater than the element in the middle position, then the target value is in the
    upper half of the array. We ignore that part of the array that does not contain the target value and
    then find the middle index position of that part of the array that does. Compare the target value to
    the element in the middle position: is it equal to, less than or greater than the target value? By
    repeating the process, we will either find the target value or determine it is not present.

    As an example of a binary search, consider the following sorted list:

    2 3 4 7 12 18 23 29 31 37 38 49 53

    A binary search involves comparing a search value with the middle (median) number in a list
    (23), or one number away from this middle number if there is an even number of numbers in the
    sorted list. If the middle number matches the search value, then the search is completed. If the
    search value is less than the middle number in the list, then numbers left of this middle number are
    searched (left-hand list). If the search value is greater than the middle number in the list, then
    numbers right of this middle number are searched (right-hand list). The technique used to search
    the left-hand or right-hand list is also a binary search; hence the search algorithm will call itself
    recursively.

    The logic behind a linear search is:

    1. Enter in the value to search for


    2. Find the middle index of the array and compare this value to the search value
    3. Either the search value is found or the search value is above or below the middle value
    4. If the search value is above the middle, set the (new) bottom value to this middle value +1, or
    if below the middle value, set the (new) top value to this middle value -1
    5. Continue the above process until either the search value is found or there are no more items
    to find

    A binary search is extremely effective. This efficiency lies in the continual halving of the list
    being searched. A list containing 100,000 items will, after 1 comparison, be reduced to 50,000
    items; after 2 comparisons to 25,000 items; after 3 comparisons to 12,500 items; and so on. For
    100,000 items, it will take a maximum of 17 comparisons to locate a specific item in a list. As 2​16
    items =65,536 and 2​17 items = 131,072, and there are 100,000 items, and 100,000 lies between 2​16
    and 2​17​, the maximum number of comparisons is 17. In general, a list containing X items will take
    lnX/ln2 (rounded up to the next integer) comparisons to find a particular item.
    The pseudocode for a binary search is:

    BEGIN
    Set lower to first index
    Set upper to last index
    found = false
    Get value to find
    WHILE​ found = false ​AND​ lower <= upper
    middle = integer part of (lower + upper)/2
    IF​ value = array(middle) ​THEN
    Found = true
    PositionFound = middle
    ELSE
    IF​ value < array(middle) THEN
    upper = middle – 1
    ELSE
    lower = middle + 1
    ENDIF
    ENDIF
    ENDWHILE
    IF​ found = true ​THEN
    Display PositionFound
    ELSE
    Display item not found
    ENDIF
    END

    You might also like