kumar wrote: > Let A is an array of positive or negative > integers of size n, where A[1] < A[2] < A[3] < ... < A[n]. Write an > algorithm to find an i such that A[i] = i provided such i exists. What > is the order of execution time of algorithm. Prove that O ( log n ) is > the best possible..
Atamyrat didn't mention that the quantity A[i] - i is non-decreasing and has a zero if and only if there exists A[i]==i for some i. To find a zero, the formal name for what you want is "bisection", which is a binary search for a zero. You start with a search bracket [1..n] where A[1]-1 and A[n]-n either include a zero or have opposite signs. In the latter case, check the sign of the middle of the bracket and shrink the bracket toward the middle as long as the signs are different. Proving O(log n) is the best possible is a trivial information theoretic adversary argument based on the sure fact that there are n possible answers. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
