Combining two functions 1]Bubble Sort 2]Binary Search

Question

I have an assingment. the assingment says to write two functions in python that will:

1. Sort the the list using bubble Sort
2. Take numerical input from the user and search the previously sorted list for that number.

My first function - sort - can sort. However, my second function is not performing a binary search correctly. My end goal is to combine the two functions.

Here is my current code:

Bubble Sort

def sort(x):
        for j in range(len(x)):
            for i in range (len(x)-1):
                if x[i]> x[i+1]:
                    temp =x[i]
                    x[i]=x[i+1]
                    x[i+1]=temp
        return x

    sl = sort([87,56,34,23,89,15,2,200,28,31])
    print (sl)         

Binary Search

def bs(t):

    s = 0 
    e = len(t)-1
    found = False
    c = int(input("Enter"))
    while (s<=e):
        mid = (s+e)//2
        if t[mid]==c:
            found = True
        elif c > t[mid]:
            s = mid+1
        else:
            e = mid-1
    return found
bs([1,2,3,4,5])

Answer 1

The problem is in your while loop. In case item is found s or e not increment/decrement and loop becomes infinite.

You should add break statement or split if conditions:

def bs(t):
    t = sort(t)

    s = 0 
    e = len(t)-1
    found = False
    c = int(input("Enter"))
    while (s<=e):
        mid = (s+e)//2
        if t[mid]==c:
            found = True
            break
        elif c > t[mid]:
            s = mid+1
        else:
            e = mid-1
    return found
bs([1,2,3,4,5])

or:

def bs(t):
    t = sort(t)

    s = 0 
    e = len(t)-1
    found = False
    c = int(input("Enter"))
    while (s<=e):
        mid = (s+e)//2
        if t[mid]==c:
            found = True

        if c > t[mid]:
            s = mid+1
        else:
            e = mid-1
    return found
bs([1,2,3,4,5])

combined function ( sort + bs ):

def binary_search(x):
for j in range(len(x)):
    for i in range(len(x) - 1):
        if x[i] > x[i + 1]:
            temp = x[i]
            x[i] = x[i + 1]
            x[i + 1] = temp

    s = 0
    e = len(x)-1
    found = False
    c = int(input("Enter"))

    while s <= e:
        mid = (s + e)//2
        if x[mid] == c:
            found = True
            break
        elif c > x[mid]:
            s = mid+1
        else:
            e = mid-1

    return found

combined with some refactoring:

def binary_search(x):
    # j is not used, so it could be replaced with underscore
    for _ in range(len(x)):
        for i in range(len(x)-1):
            if x[i] > x[i+1]:
                # this is illustration of python awesomeness
                x[i], x[i+1] = x[i+1], x[i]

    c = int(input("Enter"))

    while x:
        # this line is actually the same as s + e, because 
        # is always equals to list's len - 1
        mid = (len(x)-1)//2

        # instead of redefining variable - just break from loop
        if x[mid] == c:
            break

        if c > x[mid]:
            # slice list instead of computing new start index
            x = x[mid+1:]
        else:
            # slice list instead of computing new last index
            x = x[:mid-1]

    return len(x) > 0  # true if x contains at least one el and false otherwise 


sl = binary_search([87, 56, 34, 23, 89, 15, 2, 200, 28, 31])
print(sl)