Returning the number before a given number in a list

Question

I am trying to write a binary search that will yield the highest number before a given number in an ordered list.

y = int(input("Enter a number:"))
numblist = [5, 8, 9, 10, 18, 20, 25, 28, 30, 35]

lowerval = numblist[0]
higherval = numblist[9]
number = 0

mid = (higherval + lowerval)//2

for y in numblist:
   number += 1
if mid == y:
   print(number)
   break

if mid < y:
    lowerval = mid
else:
    higherval = mid
    mid = (higherval + lowerval)//2

For example, if I input 20, the number returned should be 18. I honestly do not know how to call the right location. I am extremely new at python, so any help would be appreciated.

Answer 1

Here is a recursive algorithm for a binary search to find the index of the element that is less than x in arr:

def binary_search_lessthan(x, arr, offset=0):
    arr = sorted(arr)
    ix = len(arr)//2
    if x==arr[ix]:
        return ix+offset-1
    elif x<arr[ix]:
        if len(arr)==1:
            return offset-1
        return binary_search_previous(x, arr[:ix], offset)
    elif x>arr[ix]:
        if len(arr)==1:
            return offset
        return binary_search_previous(x, arr[ix:], offset+ix)

Note that this returns -1 if the value is less than the first value in the list

>>>a = [5, 8, 9, 10, 18, 20, 25, 28, 30, 35]
>>>binary_search_lessthan(19, a)
4
>>>a[binary_search_lessthan(29, a)]
28
>>>a[binary_search_lessthan(9, a)]
8
>>>a[binary_search_lessthan(8, a)]
4

Answer 2

It seems like, given your code, there's a conceptual problem with binary search. If we tackle that first the code should make more sense.

What is binary search?

Given an ordered list, and an item that you're searching for, you halve the list and look at each half in turn. Let's look at this with an example. Given [1, 2, 3, 4, 5, 6] and searching for 5 you look at the two halves of the list [1,2,3] and [4,5,6]. Looking at the first half ([1,2,3]), you notice that the largest item is 3. Given that the list is ordered, all the items in the list must be smaller than 3. This means that it is not possible for 5 (what you're searching for), to be in the smaller list. You now look at ([4,5,6]). Lets break that into two lists [4] and [5,6], and so on.

How do I apply binary search to my problem

Given a list of numbers and a search term, you need to return the largest item in the list that is still smaller than the search term.

Split the list into two equal halves (as equal as you can get them, odd sized lists are always going to be uneven). Look at the smallest item in the second half-list. If the smallest item is larger than the search term, then you know that the value you're looking for is in the first half-list. Otherwise, it's in the second half-list. Keep splitting the list up until you get to what you need.

What does the code look like

def largest_item_less_than_x(x, list_of_vals):
    size = len(list_of_vals)

    if (size == 0):
        return None

    if (size == 1):
        if (list_of_vals[1] < x):
            return list_of_vals[1]
        else:
            return None
    else:
        mid = size // 2
        left_half_list = list_of_vals[0:mid]
        right_half_list = list_of_vals[mid:]

        if (right_half_list[0] < x):
            return largest_item_less_than_x(x, right_half_list)
        else:
            return largest_item_less_than_x(x, left_half_list)

Lets walk through the code. If you give it an empty list it returns None. That is, given no elements to choose from, searching for an item returns nothing.

If you give it a single list with a value larger than what you're searching for, it returns None i.e. given [6] and searching for 3, well you won't be able to find what you're looking for.

If you give it a single list with a value smaller than what you're searching for, it returns that value.

If you give it a list of more than one item, then it breaks the list into two halves and searches each half recursively.

Hope that made sense.

Answer 3

There are a few problems with your code. First, you are overwriting the input variable y in your for loop statement. Secondly, the code is not properly indented inside the for loop (maybe just an error in your post?).

Some tips for getting the binary search going:

1. Try to start in the middle of the list numblist. Check to see if the number is equal, greater than, or less than and continue accordingly.
2. Use the middle index rather than finding the middle between the highest and lowest values. This way you will actually be dividing the list in half each time.
3. You might also want to consider a while loop instead of a for loop. Just a suggestion.
4. Is it safe to assume that the list will always be sorted like your example? If not you may want to add a step that sorts the list.

Here is a little code that outlines my advice and seems to work. Probably not the final answer but should help.

y = int(input("Enter a number:"))
numblist = [5, 8, 9, 10, 18, 20, 25, 28, 30, 35]

found = False
while not found:
    print numblist
    mid = len(numblist)/2  # integer div in python 2
    if (y == numblist[mid]):
        found = True
        x = numblist[mid - 1]
    elif len(numblist) == 1:
        found = True
        x = numblist[0]
    elif y < numblist[mid]:
        # search in the lower half
        numblist = numblist[0:mid]
    else:
        # Search in the upper half
        numblist = numblist[mid:]

print x

Answer 4

One question, is your list really in ascending order? Regardless I think what you could is this,

y = int(input("Enter a number:"))
numblist = [5, 8, 9, 10, 18, 20, 25, 28, 30, 35]
tempNum = 0
index = 0
tempIndex = 0
for nums in numblist:
   tempIndex++
   if nums != y:
      if nums > tempNum:
         tempNum = nums
         index = tempIndex
   else:
      break
print(tempNum)
print(numblist[index])

So this loops each indexes of your numblist. Then it asks if the current occurrence is equal to the number you enter. If yes it exits the loop, if not, it then compare the amount of the previous and current occurrence. After it found the number you enter in the list, it then exits the loop. And in the last statement you can print either the tempNum that contains the highest number before the occurrence happen, or the numblist indexing the largest number in its list. Hope you can understand my english.

Answer 5

This code should let you do what you're asking, though I'm not sure if the user is required to enter a number that is in the list.

def bin_search(arr,low,high,elem):
    mid = (low + high)//2
    if low <= high:
        # found element or hit end of list
        if mid == 0 or mid == len(arr) -1 or arr[mid] < elem and arr[mid+1] >= elem:
            print(arr[mid])
            return
        if arr[mid] < elem:
            bin_search(arr,mid+1,high,elem)
        else:
            bin_search(arr,low,mid-1,elem)



y = int(input("Enter a number: "))
numblist = [5, 8, 9, 10, 18, 20, 25, 28, 30, 35]

lowerval = numblist[0]
higherval = numblist[-1]

# special cases 

# highest value is smaller
if higherval < y:
    print(higherval)
# no such value is larger
elif lowerval > y:
    print("-1")
else:
    bin_search(numblist,0,len(numblist)-1,y)

Answer 6

The following code snippet will do what you wanted, although in a relatively clumsy (but easier to understand) fashion:

# Ask the user for an input
y = int(input("Enter a number: "))
# List of numbers to be searched
numblist = [5, 8, 9, 10, 18, 20, 25, 28, 30, 35]

# Set the lower bound of the search
lowerval = numblist[0]
# Set the upper bound of the search
higherval = numblist[-1]


# Search Algorithm
while True:
    mid = (lowerval + higherval) // 2
    if mid == y:
        # Here, I am assuming that you will only test against a list with only unique values.
        # It first indexes the value that was found, then subtracts one from it to obtain the value prior to the found value.
        print(numblist[numblist.index(y) - 1])
        # Then it exits the while loop.
        break
    if mid < y:
        lowerval = mid
    if mid > y:
        higherval = mid

Hope this helped!