dichotomize: if current range is [m M], find if mid=(m+M)/2 is on the increasing side or decreasing side. To that effect, lookup the elements following 'mid' position and see if they are increasing or decreasing. If increasing, m = mid. Otherwise M = mid.
dichotomize: if current range is [m M], find if mid=(m+M)/2 is on the increasing side or decreasing side.
ReplyDeleteTo that effect, lookup the elements following 'mid' position and see if they are increasing or decreasing.
If increasing, m = mid. Otherwise M = mid.
-> log(N), without any real worse case actually.