Running time of binary search

Question

Assume I have regular binary search, but I change the mid to 2/3*(min+max).
Will the running time change, or remain (log(n))?

I got c1+c2*log(n)/log(3/2).

Hope you know that the mid is index ... and not the element it self in binary search ! ... — StackFlowed
– StackFlowed, Commented Nov 4, 2014 at 20:49
Admittedly had to do some back of the napkin work to make sure this wouldn't affect the correctness. — AndyG
– AndyG, Commented Nov 4, 2014 at 20:53
just use log(a)/log(b). The performance will reduce. the time complexity will be O(log(n)) — WannaBeCoder
– WannaBeCoder, Commented Nov 4, 2014 at 20:57

Zim-Zam O'Pootertoot · Accepted Answer · 2014-11-04 20:52:41Z

3

It'll still be log(n). You'll have a different log base (3/2 instead of 2), but changing a log base is the same as multiplying by a constant.

answered Nov 4, 2014 at 20:52

18.2k4 gold badges45 silver badges71 bronze badges

Sign up to request clarification or add additional context in comments.

1 Answer 1