How do you calculate number of accesses for a sequential search if record is present, not present, or sometimes present?
What about for binary search?
A:
Well, first you imagine (or draw on paper if, like me, you are imagination-challenged) a list of things to search through - keep it simple, make it an ordered list of integers. Then, think of an integer. Put your pencil (or thought) on the first element in the list, bend over the thumb on one hand and count 1 to yourself. If the first element is the one you want, write a 1 on another piece of paper, pick another number and start again. If the first number is not the one you are looking for move your pencil along one number, count 2 and bend over the index finger on your hand. Continue until you find the number you are looking for or don't.
Repeat this process until you are either bored or realise what the answers to your questions are. Please don't think of this as a sarcastic comment, it's intended to teach you how to figure this sort of thing out.
As for binary search, look at the element in the middle of the list. Count 1. Is it the element you are looking for ? If not is it larger than the element you are looking for ? If it is, then look at the middle of the left of the list, otherwise look at the middle element in the right of the list. Repeat, and count, until you find the element you are looking for.
Working through a few examples with pencil and paper is a great way of building your understanding of what the computer is doing. And, from experience, the day will come when you find yourself debugging a very tricky bit of code this way, so it will stand you in good stead should you ever graduate to programming professionally.
High Performance Mark
2010-03-16 09:17:43