Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
The sorted marks are . Use binary search to look for and for . How many steps does each take?
Look at the middle, and throw away half that cannot hold the target.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, compare your working with the solution.
Looking for . The places are to . Step 1: the middle is place , which holds . is bigger, so keep places to . Step 2: the middle is place , which holds . Found, after 2 steps.
Looking for . Step 1: place holds , which is bigger than , so keep places to . Step 2: place holds , which is smaller, so keep place . Step 3: place holds , which is bigger, and nothing is left. Not found, after 3 steps.
Log in to join the discussion.
Loading…