Binary search through strings

Question

I'm relatively new to python(3.3) and I'm just trying to do a binary search through a list of words, and cant figure out how to fix my operand types when it comes down to looping through the indices... I continue to get the TypeError. Cant figure out any way around it

def find(L, target):
 start = 0
 end = len(L) - 1
 while start <= end: 
 middle = (start + end)// 2 
 midpoint = L[middle]
 if midpoint > target:
 end = midpoint - 1
 elif midpoint < target:
 start = midpoint + 1
 else:
 return midpoint

I'm calling the function as so:

L = ["Brian", "Meg", "Peter", "Joe", "Stewie", "Lois"]

find(L, "Joe")

• Joran Beasley: binary search only works on sorted lists
• Fernando Matsumoto: midpoint is a string. What should midpoint - 1 do?
• jianweichuah: @FernandoMatsumoto might be a typo. I think he meant middle - 1, middle + 1.
• Jonathan Leffler: To do a successful binary search on an array, the data in the array must be in sorted order. The entries for all except Brian are out of position — the sequence should be Brian, Joe, Lois, Meg, Peter, Stewie.
• tdelaney: @jianweichuah I think Fernando is pointing out the bug.

Answer 1

Your logic seems fine, except for the input and the bug with incrementing and decrementing midpoint instead of middle.

def find(L, target):
 start = 0
 end = len(L) - 1
 while start <= end:
 middle = (start + end)/ 2
 midpoint = L[middle]
 if midpoint > target:
 end = middle - 1
 elif midpoint < target:
 start = middle + 1
 else:
 return midpoint
L = ["Brian", "Joe", "Lois", "Meg", "Peter", "Stewie"] # Needs to be sorted.
print find(L, "Peter")

• OneCricketeer: What if you try to find a string tha doesn't exist? What is returned?
• jianweichuah: @cricket_007 None. Not sure what the OP's use case is
• Yahya: It should be int((start + end) / 2)

Answer 2

def find(L, target):
 start = 0
 end = len(L) - 1
 while start <= end:
 middle = (start + end)// 2
 midpoint = L[middle]
 if midpoint > target:
 end = middle - 1
 elif midpoint < target:
 start = middle + 1
 else:
 return midpoint
 L = ["Brian", "Joe", "Lois", "Meg", "Peter", "Stewie"]
 L = sorted(L)
 print(find(L, "Lois"))

As pointed out by others, use middle instead of midpoint

And to optimally use binary search, sort the list first

• Fernando Matsumoto: sorted(L) returns a new sorted list with the elements of L. Either use L = sorted(L) or L.sort().

Answer 3

def binarySearchOnString(arr, x):
 l = 0
 r = len(arr) - 1
 while (l <= r): 
 m = (l + r) // 2 
 if (arr[m] == x): 
 return m
 elif (arr[m] < x): 
 l = m + 1
 else: 
 r = m - 1
 return -1 # If element is not found then it will return -1