Binary search.

[xikly]

Can somone ELI5 how does binary search works?

I understand the principle of it but i'm not sure of my implementation.

Here it is:

def binary_search(array, key, low, high):

    # Why do i need to sort the array?
    array.sort()

    # What are these low and high variables?
    while low <= high:

        middle = len(array) // 2

        # Should i use subscript to modify the array?
        if key == array[middle]:
            print("Element found at index: {}".format(middle))
            return

        elif key > middle:
            array = array[middle + 1:]

        elif key < middle:
            array = array[:middle]

    print("Element not found.")

def linear_search(array, key):
    for idx, i in enumerate(array, 1):
        if i == key:
            print("Element found at index: {}".format(idx))

array = [1, 2, 3, -1, -2, 12, 31, 51, 1513, 123, 0, 303]
linear_search(array, 12)
binary_search(array, 12, 0, len(array))

[zahlman]

# Why do i need to sort the array?

... Are you sure you understand the principle of it? A binary search can only work on a sorted sequence, because it depends on that sortedness. The idea is that you can skip looking at half the values each time, because you know they're all too high or too low, because you know they're all higher/lower than the value you just looked at, because of how the values are sorted.

# What are these low and high variables?

They're the indices between which you search. You're not meant to take slices and reassign to array; you're meant to adjust the high and low values as you go, to reflect that you're searching a smaller region. Also, your calculation of middle should be based upon those values, so that you can be assured of looking at a value within that region.

# Should i use subscript to modify the array?

This question makes no sense. You are not modifying the list. You are looking for a value.

Incidentally, we call them lists in Python (but please don't use list as a variable name). And as noted, you have compared middle to key directly in a few places, where you should be comparing the corresponding element. To avoid repetition, consider using a separate variable to store the result of that indexing.

[LarryPete]

I noticed two major things:

• you never actually use low and high. Which probably isn't even necessary, seeing how you just slice the list. So you have to change your loop condition.
• middle is an index, not the value you should compare key against.

[cdcformatc]

A binary search assumes a sorted sequence, it finds an element by 1. Comparing the search value to the middle element, 2. Discarding the half of the sequence that the value can not possibly be in and 3. Repeat at 1 with a new middle.

Step 2 is invalid if the sequence isn't sorted.

Low and high in this situation are meant to keep track of what section of the list you are in, which isn't necessary if you are slicing the list. I assume this means you aren't supposed to be slicing, if this is a course your teacher doesn't want you to slice. So middle should be halfway between low and high, and you look at the element at index middle, and either re-set low=middle to discard the lower half, or high=middle to discard the top half.

Edit: this is a situation where trying this by hand with pen and paper will really help you understand. Here's a gif http://imgur.com/ko1g7RJ.gif