I don't understand something about Python. This is binary search code and when i put if
statement with return first it works, but when I put it below the another if
statement something goes wrong. Could someone explain this?
def binary_search(arr, item):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low high)//2
guess = arr[mid]
if guess == item:
return mid
if guess > item:
high = mid - 1
else:
low = mid 1
return None
arr = [1, 12, 16, 22, 24, 45, 54, 67, 89, 121]
print(binary_search(arr, 54))
Output: 6
def binary_search(arr, item):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low high)//2
guess = arr[mid]
if guess > item:
high = mid - 1
if guess == item:
return mid
else:
low = mid 1
return None
arr = [1, 12, 16, 22, 24, 45, 54, 67, 89, 121]
print(binary_search(arr, 54))
Output: None
I thought the operations python does in both cases are the same, but it seems I'm wrong.
CodePudding user response:
Try to iterate the code you have by yourself. The second example would work like this:
0 | low = 0 high = 9 -> mid = 4
1 | low = 5 high = 9 -> mid = 7
2 | low = 8 high = 9 -> stop
If statements behave like this because your condition on guess > item
and guess < item
are not bound to each other meaning that they could be both checked and, therefore, run. This is what actually happens after third iteration, high
should go lower and not the low
higher
CodePudding user response:
Here I fixed it for you and it print out as your first code. if,elif and else are binded into one condition. It first check if then, elif and finally else.
def binary_search(arr, item):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low high)//2
guess = arr[mid]
if guess > item:
high = mid - 1
elif guess == item:
return mid
else:
low = mid 1
return None
arr = [1, 12, 16, 22, 24, 45, 54, 67, 89, 121]
print(binary_search(arr, 54))