search magic index in sorted array

If i = a[i], then i is magic index.

Divide into two parts and search left or right. For duplicates, search both.

// search left
index: 012-3-45
array: 023-5-67

// search right
index: 012-3-45
array: ..0-1-35

search(a):
    return search(a, 0, a.length-1)

// assume no duplicates
search(a, start, end):
    if start > end:
        return -1
    mid = (start+end) /2
    if mid < a[mid]:
        // search left
        return search(a, start, mid-1)
    if mid > a[mid]:
        // search right
        return search(a, mid+1, end)
    return mid

// for duplicates, search both
index: 012-3-45
array: 000-2-55

index: 012-3-45
array: 000-4-55

// search left, and portion of right
index: 012-3-45
array: ...-5-55

// search right, and portion of left
index: 012-3-45
array: 111-1-..

// with duplicates
search(a, start, end):
    if start > end:
        return -1
    mid = (start+end) /2
    if mid < a[mid]:
        // search left first
        index = search(a, start, mid-1)
        if index != -1:
            return index
        // search portion of right
        return search(a, a[mid], end)
    if mid > a[mid]:
        // search right first
        index = search(a, mid+1, end)
        if index != -1:
            return index
        // search portion of left
        return search(a, start, a[mid])
    return mid

// worst cases
index: 012-3-45
array: 123-4-56
array: ..1-2-34

[Hat tip to ctci]