binary search complexity
Hello..how to calculate the best case complexity and the worst case complexity and the average complexity for this algorithm with proof:
binary search(A , l , r , sv)
q=(1+r)/2
if A[q]=sv then return q
elseif A[q]>sv then binary search(A , l , q , sv)
else binary search(A , q , r , sv)
binary search(A , l , r , sv)
q=(1+r)/2
if A[q]=sv then return q
elseif A[q]>sv then binary search(A , l , q , sv)
else binary search(A , q , r , sv)
How to calculate any complexity? I can't remember, but a websearch with "binary search complexity" is likely to spoil the fun.
think about it a bit.
if you search for a value in your data and get really, really, really lucky and that piece of data is in the first location that you looked at, how much work did you do?
if the data is not there at all, how much work do you have to do to figure that out?
start there. the first one should be very, very obvious. The second one is a little more trouble, but its very simple math to describe it -- you cut the list in half every time, discarding the half that cannot possibly contain the value. if you had 100 items, its not there... cut in half once, 50, 25, 13, 7,4,2,1 ...7 searches... how can we describe this?? what is 2 to the 7th power? what is 2 to the 6th power? How are logs related to powers?
if you search for a value in your data and get really, really, really lucky and that piece of data is in the first location that you looked at, how much work did you do?
if the data is not there at all, how much work do you have to do to figure that out?
start there. the first one should be very, very obvious. The second one is a little more trouble, but its very simple math to describe it -- you cut the list in half every time, discarding the half that cannot possibly contain the value. if you had 100 items, its not there... cut in half once, 50, 25, 13, 7,4,2,1 ...7 searches... how can we describe this?? what is 2 to the 7th power? what is 2 to the 6th power? How are logs related to powers?
Topic archived. No new replies allowed.