Combining two functions 1]Bubble Sort 2]Binary Search [closed]

–2 votes
asked Sep 12, 2017 by subha-saha

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])

1 Answer

+1 vote
answered Mar 12, 2018 by yaroslav-surzhikov

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)
Welcome to Q&A, where you can ask questions and receive answers from other members of the community.
...