I was given the following code and was told to find the best and worst case running times in big theta notation. (Below is in python)
def find(a, target):
x = 0
y = len(a)
while x < y:
m = (x+y)/2
if a[m] < target:
x = m+1
elif a[m] > target:
y = m
else:
return m
return -1
I know that the running time of this code in the worst case is O(lg(n))$O(\lg n)$. But the question I was given if the fifth line was changed from "m=(x+y)/2"$m = \frac{x+y}{2}$ to "m=(2*x+y)/3"$m=\frac{2x+y}{3}$, would the running time change?
My intuition is that the running time gets a little larger as it is no longer cutting the list in half like binary search should do which is less efficient, but I am not sure how to calculate what big Othe asymptotic runtime would be at this point.