basic binary search

[deep_logic]

Hi all,
I have googled and researched this problem. I'm just trying to do a binary search program. I'm using "Grokking Algorithms" from Agitya.

I'm a self student, so this is purely for me to enhance my coding skills. Here is what I've got:

###Binary Search
###R. Long 09/20/19
###

low = 0
high = len(list) - 1

mid = (low + high) / 2
guess = list[mid]

if guess < item:
     low = mid + 1

def binary_search(list, item):
    low = 0
    high = len(list)-1

    while low <= high:
            mid = (low + high)
            gues = list[mid]
            if guess == item:
                return mid
            if guess > item:
                high = mid - 1
            else:
                low = mid + 1
            return None

        my_list = [1, 3, 5, 7, 9]

        print binary_search(my_list, 3) # => 1
        print binary_search(my_list, -1) # => None
      

        

I keep getting, "unindent does not match any outer indentation level".
I'm not really sure where the indentation level is.
I'm on python 2.7 and win10.

Thanks for any help

[ichabod801]

Line 29 should be flush left. The error comes from the whitespace on the left of line 29 not being the same as any of the white space above it.

Next time please post the full text of the error you get.

[ThomasL]

Your indention was quite messed up

def binary_search(numbers, item):  # don´t use list as variable name as this is a python type and keyword for list data structure
    low = 0
    high = len(numbers) - 1
    while low <= high:
        # mid = low + high    # this is wrong; you are selecting the last item in the list
        mid = (low + high) // 2
        guess = numbers[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    return None

numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25]

# i´m using python 3
print(binary_search(numbers, 7)) # => 3
print(binary_search(numbers, 4)) # => None

[deep_logic]

@ThomasL

I ran your code edits and I'm still getting an error:

Error:
Traceback (most recent call last):
  File "C:/Users/araki/AppData/Local/Programs/Python/Python37-32/binary search.py", line 19, in <module>
    print (binary_search(numbers, 7)) # => 1
NameError: name 'numbers' is not defined

I'm using IDLE 3.7. I'm wondering if there is something wrong with my version/install?

---

ok, ok, I found my bug. I forgot to change the list to numbers variable.

So...it ran without error, but the output is:

Output:
3
None

Not sure what it's saying here. Is it saying 3 is the mid point of the list?

[newbieAuggie2019]

So...it ran without error, but the output is:

Output:
3
None

Not sure what it's saying here. Is it saying 3 is the mid point of the list?

Hi!

As ThomasL indicated in the comments for the examples he provided for you:

numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25]

# i´m using python 3
print(binary_search(numbers, 7)) # => 3
print(binary_search(numbers, 4)) # => None

3, and None were the expected output.

He meant that with those 2 lines, he made the program do a binary search for the numbers '7' and '4' in the list named 'numbers'.

The output for searching '7' is 3; that means that '7' is present in the list named 'numbers' in the position '3'. Remember that lists start with position '0'; so in position '0' you have the number '1', in position '1' you have the number '3', in position '2' you have the number '5', in position '3' you have the number '7', and so on.

The output for searching '4' is None; that means that '4' is not present in the list named 'numbers', so it says that '4' is in the position None, because it is present in None of the positions of the list named 'numbers'.

All the best,

---

I just modified the program TomasL made for you, by changing the last two lines to explain themselves and then, I added also a small loop, where the program asks you 16 times for a number to be checked if it is in the List named "numbers" or not (the range(1, 17) means it starts from the number 1 included, and as with the range() function, the upper limit is excluded, this means 17 is not included, so it actually does it only to a 16th time). In this way you can check the position of every element in the list, and also some that they are not in it:

def binary_search(numbers, item):  
    low = 0
    high = len(numbers) - 1
    while low <= high:
        mid = (low + high) // 2
        guess = numbers[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    return None
 
numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25]
 
# i´m using python 3
print(f'The binary search for number 7, resulted to be in position "{binary_search(numbers, 7)}" in the list named "numbers" = {numbers}.') # => 3
print(f'The binary search for number 4, resulted to be in position "{binary_search(numbers, 4)}" in the list named "numbers" = {numbers}.\n') # => None

for x in range(1, 17):
    n1 = input('Please, enter a number to check if it is in the list named "numbers":\n')         
    print(f'''The number '{n1}', resulted to be in position "{binary_search(numbers, int(n1))}" in the list named "numbers" = {numbers}.''')

so the output is like this:

Output:
The binary search for number 7, resulted to be in position "3" in the list named "numbers" = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25].
The binary search for number 4, resulted to be in position "None" in the list named "numbers" = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25].

Please, enter a number to check if it is in the list named "numbers":
1
The number '1', resulted to be in position "0" in the list named "numbers" = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25].
Please, enter a number to check if it is in the list named "numbers":
3
The number '3', resulted to be in position "1" in the list named "numbers" = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25].
Please, enter a number to check if it is in the list named "numbers":
5
The number '5', resulted to be in position "2" in the list named "numbers" = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25].
Please, enter a number to check if it is in the list named "numbers":
7
The number '7', resulted to be in position "3" in the list named "numbers" = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25].
Please, enter a number to check if it is in the list named "numbers":
9
The number '9', resulted to be in position "4" in the list named "numbers" = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25].
Please, enter a number to check if it is in the list named "numbers":
11
The number '11', resulted to be in position "5" in the list named "numbers" = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25].
Please, enter a number to check if it is in the list named "numbers":
13
The number '13', resulted to be in position "6" in the list named "numbers" = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25].
Please, enter a number to check if it is in the list named "numbers":
15
The number '15', resulted to be in position "7" in the list named "numbers" = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25].
Please, enter a number to check if it is in the list named "numbers":
17
The number '17', resulted to be in position "8" in the list named "numbers" = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25].
Please, enter a number to check if it is in the list named "numbers":
19
The number '19', resulted to be in position "9" in the list named "numbers" = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25].
Please, enter a number to check if it is in the list named "numbers":
21
The number '21', resulted to be in position "10" in the list named "numbers" = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25].
Please, enter a number to check if it is in the list named "numbers":
23
The number '23', resulted to be in position "11" in the list named "numbers" = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25].
Please, enter a number to check if it is in the list named "numbers":
25
The number '25', resulted to be in position "12" in the list named "numbers" = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25].
Please, enter a number to check if it is in the list named "numbers":
26
The number '26', resulted to be in position "None" in the list named "numbers" = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25].
Please, enter a number to check if it is in the list named "numbers":
2
The number '2', resulted to be in position "None" in the list named "numbers" = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25].
Please, enter a number to check if it is in the list named "numbers":
8
The number '8', resulted to be in position "None" in the list named "numbers" = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25].
>>> 

I hope this helps you to see and understand the positions of the elements in a list.

All the best,