the array 2,2,2 is nondecreasing, but is ascending. but the array 1,2,3 is both nondecreasing and ascending
I must also point out something that everybody knows, but it is important not to ignore it, mostly on exams. it is that O(log n) is also O(n). So if you say that algorithm complexity is O(n) it does not imply that it is not O(log n) You should use Omega instead, if something is Omega(n), then it is not O(log n), however it is Omega( log N) Thx 2009/3/4 sharad kumar <[email protected]> > 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 <[email protected]>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 <[email protected]> >> >> >>> 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 <[email protected]> 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 >>> >>> >> >> >> > > > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
