Editing Binary search

Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

Binary search is a search algorithm to find a value in a sorted array. It works by starting at the middle of the array and checking if the target value is higher or lower than the middle value. If it is lower, the algorithm then treats the bottom half as the new array and repeats the process of checking the middle value until the target value is found. If the target is higher than the midpoint, the top half of the array is used.

Example in Python:

<syntaxhighlight lang="python3" line="1">
def binary_search(array, target):
    min = 0
    max = len(array)
    while min <= max:
        mid = (min + max) // 2
        if array[mid] < target:
            min = mid + 1
        elif array[mid] > target:
            max = mid - 1
        else:
            return mid
    # Not found
    return -1
</syntaxhighlight>

=== Purpose ===
The advantage of using binary search over a simpler "check every element" approach is speed. Since each step of the algorithm approximately halves the number of elements that need to be searched, each doubling of the size of the array only adds one iteration to the "while" loop above, as opposed to doubling the number of iterations. In other words, the number of steps required grows in proportion with the base-2 logarithm of the size of the array. In algorithmic complexity notation, binary search has O(log n) time complexity.

Summary:

Please note that all contributions to PASTE Wiki may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see PASTE Wiki:Copyrights for details). Do not submit copyrighted work without permission!

Cancel Editing help (opens in new window)

Retrieved from "https://paste.voklen.com/wiki/Binary_search"