search x in sorted but rotated array

Divide into two parts. Either left or right part would be ascending. If x lies in the ascending part, search in it else search the other part. For duplicates, search both parts.

// 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]