hmm...... worst case will be O(n). m not sure but i think avg case would be logn + k ( now if k approx logn ( k<<n) where k is the number of times an element can repeat itself the order remains same) now if k is large, no of different elements is v low, many times unsucc search will happen which is logn rigrous analysis has to be done.
Anyways my second soltn is definitly O(logn) where u chk the highest number instead of mid. On Wed, Mar 4, 2009 at 7:43 PM, sharad kumar <aryansmit3...@gmail.com> wrote: > ya boss rite.but according to asymptotic analysis the solutin shld be > O(n);rite?? > > On Wed, Mar 4, 2009 at 6:48 PM, Prakhar Jain <prakh...@gmail.com> wrote: >> >> see its log(n) + k where k<=the number of duplicates of the element >> being searched. >> For log(n), you can continue till your high comes on the element u >> desire and not low. >> >> >> On Wed, Mar 4, 2009 at 6:45 PM, sharad kumar <aryansmit3...@gmail.com> >> wrote: >> > "search() find any index and then iterates sequentially till the highest >> > index" how is this logn >> > >> > On Wed, Mar 4, 2009 at 6:44 PM, sharad kumar <aryansmit3...@gmail.com> >> > wrote: >> >> >> >> ya rite.... >> >> >> >> On Wed, Mar 4, 2009 at 5:31 PM, Prunthaban <pruntha...@gmail.com> >> >> wrote: >> >>> >> >>> @sharad - Your solution is O(n) Miroslav's solution is O(logn). >> >>> And what are you doing with the 'j' variable in your solution? Why not >> >>> simply use a[i] == k then c = i. That is what eventually your solution >> >>> is doing and it is O(n). >> >>> >> >>> >> >>> >> >>> On Mar 4, 4:32 pm, sharad kumar <aryansmit3...@gmail.com> wrote: >> >>> > pls tell wats difference btwn increasing and non decresing sorted >> >>> > array.question clearly tells n sorted array....... >> >>> > >> >>> > On Wed, Mar 4, 2009 at 4:55 PM, Miroslav Balaz >> >>> > <gpsla...@googlemail.com>wrote: >> >>> > >> >>> > > of course, you cannot assume that array is in ascending order, it >> >>> > > is >> >>> > > in >> >>> > > non-decreasing order however not in ascending >> >>> > > and you should swap order here :(a[mid+1] > key||mid==high) >> >>> > >> >>> > > 2009/3/4 Kapil <navka...@gmail.com> >> >>> > >> >>> > >> just fixing a bug >> >>> > >> >>> > >> what if you write bin_search as this >> >>> > >> //assumption array is in ascending order >> >>> > >> binsearch(high, low, key, a) >> >>> > >> begin >> >>> > >> if low > high >> >>> > >> return -1 >> >>> > >> mid = (high+low)/2 >> >>> > >> if a[mid] = key And (a[mid+1] > key||mid==high) >> >>> > >> return mid >> >>> > >> if a[mid] <= key >> >>> > >> low = mid+1 >> >>> > >> else >> >>> > >> high = mid - 1 >> >>> > >> return binsearch(high,low,key,a) >> >>> > >> end >> >>> > >> >>> > >> On Mar 4, 3:46 pm, Kapil <navka...@gmail.com> wrote: >> >>> > >> > what if you write bin_search as this >> >>> > >> > //assumption array is in ascending order >> >>> > >> > binsearch(high, low, key, a) >> >>> > >> > begin >> >>> > >> > if low > high >> >>> > >> > return -1 >> >>> > >> > mid = (high+low)/2 >> >>> > >> > if a[mid] = key And a[mid+1] > key >> >>> > >> > return mid >> >>> > >> > if a[mid] <= key >> >>> > >> > low = mid+1 >> >>> > >> > else >> >>> > >> > high = mid - 1 >> >>> > >> > return binsearch(high,low,key,a) >> >>> > >> > end >> >>> >> >> >> > >> > >> > > >> > >> >> >> >> -- >> Prakhar >> >> > > > > > -- Prakhar --~--~---------~--~----~------------~-------~--~----~ 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 algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
