So from the sound of your question you are attempting to get a binary search working for your example. First, it is useful to know that a binary search only works reliably on sorted data. This is quite different than a standard linear search that will always find the value, regardless of order. As you likely already know binary search is preferred because it eliminates half of the potential candidates per iteration, whereas linear search only eliminates one element. With that said, let’s discuss the modifications I have made to your program. First, some cosmetic changes can greatly increase the clarity of your program.
1.) Using descriptive variable names is very important and serves as a note to others reading your code, on what the contents and function of a variable might be. This is especially important in a language like python where variable types are not easily inferred just by reading the code. So instead of reusing the variable i multiple times, I have renamed your function parameter target as that is the search term we are attempting to locate, i.e. our ‘target’. I also renamed your function from ‘bsort’ which implies that the function sorts something, to ‘bsearch’ which is a more appropriate name because it more accurately describes what the function does.
2.) Binary search can be implemented using a loop or recursion. For simplicity, I have selected the iterative route using a loop. As I mentioned before, binary search works by eliminating half of the potential search candidates each iteration. Without the loop, you do eliminate half of the candidates (only one time), but unless you are extremely lucky you will likely not find the term you are searching for! Instead you need to continue this process until you have located the term you are searching for. This is the function of the while True: loop.
3.) Finally, we have made sure that we are using integers to access the indices of our list. All lists in python are indexed from 0 to n-1 where n is the number of elements in a list. We cannot access a list using a floating point value such as 2.5 because this does not correspond to any specific ‘slot’ in the list. Similarly, we cannot use a string to access our elements because a list again requires a integer to perform a lookup. This is the purpose of mid = int((left + right)/2).
With all that said, this should work for your intended purpose. I hope this helps you! I also encourage you to take a look at some examples of how to implement a binary search such as this one.
def bsearch(alist, target):
left = 0
right = len(alist)-1
while True:
mid = int((left + right)/2)
if alist[mid] < target :
left = mid + 1
elif alist[mid] > target :
right = mid + 1
elif alist[mid] == target :
print ("word '" + target + "' found at " + str(mid))
break
elif left > right:
print ("Not Found!")
break
i = input("Enter a search >")
alist = ["rat","cat","bat","sat","spat"]
alist.sort()
bsearch(alist, i)
2
solved How to implement a binary search?