Trying to make a function hat halves a list for a binary search


#1



Traceback (most recent call last):
File "/Volumes/ELEMENTS/binary search.py", line 26, in
if which_half_of_the_list(lists, 5) == True:
File "/Volumes/ELEMENTS/binary search.py", line 14, in which_half_of_the_list
list_number += int(list_of_numbers(sequence))
TypeError: 'list' object is not callable


i expected my code to print found


lists = [1,2,3,4,5,6,7,8,9]

def which_half_of_the_list(list_of_numbers, chosen_number):
    sequence = 0
    a = 0
    more_or_less_than_list = []
    more_than = False
    less_than = False
    for count in list_of_numbers:
        a += 1
        sequence += 1
    sequence = sequence // 2
    list_number = 0
    list_number += int(list_of_numbers(sequence))
    if list_number == chosen_number:
        return True
    elif list_of_numbers(sequence) > chosen_number:
        for count in range(list_of_numbers(sequence), a):
            more_or_less_than_list += count
        return more_or_less_than_list
    elif list_of_numbers(sequence) < chosen_number:
        for count in range(0, list_of_numbers(sequence)):
            more_or_less_than_list += count
        return more_or_less_than_list

if which_half_of_the_list(lists, 5) == True:
    print("found")


#2

The error message is telling you that a list object is not a function, as indicated by ().

list_object[sequence]    # list syntax

#3

i changed some of the code but now it says that Nonetype object is not iterable
the part of the code that does it is the highlighted line

def which_half_of_the_list(list_of_numbers, chosen_number,
                           more_or_less_than_list):
    sequence = 0
    a = 0
    more_or_less_than_list = []
    more_than = False
    less_than = False
    for count in list_of_numbers:
        a += 1
        sequence += 1
    sequence = sequence // 2
    if list_of_numbers[sequence] < chosen_number:
        for count in range(list_of_numbers[sequence], a):
            more_or_less_than_list.append(count)
        return more_or_less_than_list
    elif list_of_numbers[sequence] > chosen_number:
        for count in range(0, list_of_numbers[sequence]):
            more_or_less_than_list.append(count)
        return more_or_less_than_list

#4

I got your original code to work just by changing the brackets. There are a couple of unused variables, as well that I took out.


#5

ok. that is cool but in this new code, the for loop doesn't seem to be working so if you can help me with it, you would have my thanks.


#6

This is your original code with the fixes applied.

lists = [1,2,3,4,5,6,7,8,9]

def which_half_of_the_list(list_of_numbers, chosen_number):
    sequence = 0
    a = 0
    more_or_less_than_list = []
    for count in list_of_numbers:
        a += 1
        sequence += 1
    sequence = sequence // 2
    list_number = 0
    list_number += int(list_of_numbers[sequence])
    if list_number == chosen_number:
        return True
    elif list_of_numbers[sequence] > chosen_number:
        for count in range(list_of_numbers[sequence], a):
            more_or_less_than_list += count
        return more_or_less_than_list
    elif list_of_numbers[sequence] < chosen_number:
        for count in range(0, list_of_numbers[sequence]):
            more_or_less_than_list += count
        return more_or_less_than_list

if which_half_of_the_list(lists, 5) == True:
    print("found")

 found
=> None

Now let's compare this to your new code.


#7

By the term sequence do you mean literally, a sequence, as in ordered from lowest to highest with equal difference between terms? Or just a list in any order, any values.and nothing sequential about the sorted list?


#8

Assuming we are working with a sequence, this is what I have come up with as a test model/proof of concept...

def list_segment(sequence, value):
  segment_size = int(len(sequence) / 2)
  median = sequence[segment_size] if len(sequence) % 2 else 0
  if median and value == median: return "%r is the median" % value
  if value in sequence[0:segment_size]: return "%r is in low range" % value
  if value in sequence[segment_size:]: return "%r is in high range" % value
  return "%r not found in sequence" % value

lists = [1,2,3,4,5,6,7,8,9]
print (list_segment(lists, 5))
print (list_segment(lists, 3))
print (list_segment(lists, 9))
print (list_segment(lists, 4))
print (list_segment(lists, 6))
print ()
lists = [21,32,43,54,65,76,87,98]
print (list_segment(lists, 54))
print (list_segment(lists, 32))
print (list_segment(lists, 98))
print (list_segment(lists, 43))
print (list_segment(lists, 65))
print (list_segment(lists, 10))
print (list_segment(lists, 100))

5 is the median
3 is in low range
9 is in high range
4 is in low range
6 is in high range

54 is in low range
32 is in low range
98 is in high range
43 is in low range
65 is in high range
10 not found in sequence
100 not found in sequence

repl.it https://repl.it/FJaM/1


#9

i mean that it is ordered from smallest value to greatest value but the actual difference between the numbers doesn't have to be the same.


#10

what i mean to do is create a piece of code that finds the position of a number in an ordered list and prints found if it was found.


#11

that code has thrown in some unexpected errors that i don't understand how to fix. it says that the list index is out of range in line twelve and when i have tried to put sequence - 1 there it still says that.


#12

Okay, so ordered list, not sequence. The model above will still hold, without common differences. I'll take a look at your code again a little later when I have some free time. In the meantime, see if you cannot simplify the code with shorter variable names so it is easy to read. Break it down line by line and print interim results to see what is happening at each stage.


#13

thank you, i will do that


#14

Consider,

def bin_split(ol):
  # return low range, median, high range; assumes discrete ordered list
  s = len(ol)
  f = not s % 2
  n = int(s / 2)
  m = ol[n] if not f else float(ol[n] + ol[n-1]) / 2
  return (ol[:n], m, ol[n:]) if f else (ol[:n], [m], ol[n + 1:])

a,b,c = bin_split([3,6,9,12,15,18,21])
x,y,z = bin_split([3,6,9,12,15,18,21,24])

Output

 >  a,b,c
=> ([3, 6, 9], [12], [15, 18, 21])          # median is in the list
 > x,y,z
=> ([3, 6, 9, 12], 13.5, [15, 18, 21, 24])  # median not in list

Sandbox.... https://repl.it/FJaM/2


#15

thank you for your help


#16

This topic was automatically closed 7 days after the last reply. New replies are no longer allowed.