http://www.geeksforgeeks.org/archives/503
On Sun, Apr 1, 2012 at 6:54 PM, sanjiv yadav <[email protected]>wrote: > if all values x are known to be contiguous then I think it will take o(1) > time because it will be majority element if it occurs more than n/2 times > as x must be at the middle. > > so if mid=(low+high)/2 and x==a[mid]then x is majority element otherwise > not. > > just check....let me know. > > On Thu, Feb 9, 2012 at 11:40 PM, Don <[email protected]> wrote: > >> It can't be done in O(log n) unless the array is sorted or there is >> some other special property, for example, if all values x are known to >> be contiguous, allowing you to use a binary search to find the first >> and last location of x. >> >> In the general case it is impossible in O(log n) because you have to >> examine at least n/2 elements to reach a conclusion. In some cases you >> must examine all n elements. >> >> Don >> >> On Feb 8, 1:45 pm, Prakhar Jain <[email protected]> wrote: >> > Hello everyone, >> > >> > suppose we have an array of size n and a number, say x, and we have to >> > determine whether the number x is present in the array more then n/2 >> times >> > or not....? >> > can we have an O(log n) algo for determining it......?..pls help...!!! >> > >> > -- >> > -- >> > Prakhar Jain >> > IIIT Allahabad >> > B.Tech IT 3rd Year >> > Mob no: +91 9454992196 >> > E-mail: [email protected] >> > [email protected] >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > > > -- > Regards.... > > Sanjiv Yadav > > MobNo.- 8050142693 > > Email Id- [email protected] > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
