Printable View
Suppose that you are given a sorted sequence of distinct integers {a1 , a2 , . . . , an }. Give
an O(lg n) algorithm to determine whether there exists an index i such at ai = i. For example, in
{−5, −3, 3, 5, 7}, a3 = 3. In {2, 3, 4, 6, 7} there is no such i.
plz can any1 tell me a proper algorthnm for this plz/././/
O(lg n) and sorted data suggest a binary search.
Say you split the array in half. You get down to an index i and a sequence integer ai. If they're equal you have a hit. If not you must decide which half to split in half next. You do that by comparing ai with i. If ai > i there's no way there can be a hit to the right and if ai < i there's no way there can be a hit to the left. So you split accordingly and continue doing so until there's a hit or no further splitting is possible
thanks a lot dude
dude can u tell me sample algirthm for it jst a procedure is enough dude......ny way thanks for the help dude
I think you should try yourself otherwise you don't learn anything. Just slightly modify the standard recursive binary search algorithm for an element in an array.