// search right for 2 // search left for 5 index: 012-3-45 array: 456-1-23 // search both for 1 index: 012-3-45 array: 222-2-12 array: 221-2-22
// a is sorted asc but rotated search(a, x): return search(a, x, 0, a.length-1) search(a, x, start, end): if start > end: return -1 mid = start + (end-start)/2 if a[mid] == x: return mid if a[start] < a[mid]: if a[start] <= x < a[mid]: return search(a, x, start, mid-1) else: return search(a, x, mid+1, end) if a[mid] < a[end]: if a[mid] < x <= a[end]: return search(a, x, mid+1, end) else: return search(a, x, start, mid-1) // search both as a[start] == a[mid] == a[end] index = search(a, x, start, mid-1) if index != -1: return index index = search(a, x, mid+1, end) if index != -1: return index return -1
[Hat tip to ctci]
No comments:
Post a Comment