# Runtime of various versions of binary search

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)$. But the question I was given if the fifth line was changed from $m = \frac{x+y}{2}$ to $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 the asymptotic runtime would be at this point.

• How did you get to $O(\lg n)$ in the first place? Adapt your derivation to the new formula and you get your result. (By the way, similar questions have been solved in detail several times before, see algorithm-analysis.)
– Raphael
Sep 10, 2013 at 16:48
• I guess it is $\frac{2(x+y)}{3}$? Sep 10, 2013 at 17:20
• @A.Schulz, I would guess not. $(2x+y)/3$ is a weighted average of $x$ and $y$ that puts twice the weight on $x$ (i.e., it is between $x$ and $y$, but closer to $x$ than to $y$).
– D.W.
Sep 10, 2013 at 19:02