[Sorting and Searching] interview questions #3

[rygh4775]

Search in Rotated Array: Given a sorted array of n integers that has been rotated an unknown number of times, write code to find an element in the array. You may assume that the array was originally sorted in increasing order.

[btakeya]

we can assume sorting status of left half and right half array using 'array is initially increasing order'. for example, with [a, ..., b, ..., c]:

1. a < b: [a, ..., b] is increasing order. inflection point is on [b, ..., c] and b > c
2. b < c: [b, ..., c] is increasing order. inflection point is on [a, ..., b] and a > b

but should be noted, same value can be repeated. thus, example above will be edited:

1. a < b: [a, ..., b] is increasing order. inflection point is on [b, ..., c] and b >= c
2. a = b: [a, ..., b] is repeating values. [b, ..., c] may be increasing order (need to be fully scanned)
3. b < c: [b, ..., c] is increasing order. inflection point is on [a, ..., b] and a >= b
4. b = c: [b, ..., c] is repeating values. [a, ..., b] may be increasing order (need to be fully scanned)

class Node(object):
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def find_value(array, value):
    def inner(array, left, right, value):
        mid = int((left + right) / 2)
        if value is array[mid]:
            return mid

        if left > right:
            return None

        # when left is normally sorted
        if array[left] < array[mid]:
            if array[left] <= value and value < array[mid]:
                return inner(array, left, mid - 1, value)
            else:
                return inner(array, mid + 1, right, value)

        # when right is normally sorted
        elif array[mid] < array[right]:
            if array[mid] < value and value <= array[right]:
                return inner(array, mid + 1, right, value)
            else:
                return inner(array, left, mid - 1, value)

        else:
            rtmp = inner(array, mid + 1, right, value)
            return rtmp if rtmp is not None else inner(array, left, mid - 1, value)

        return None

    return inner(array, 0, len(array) - 1, value)

if __name__ == '__main__':
    rotated1 = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14]
    print(find_value(rotated1, 4))
    print(find_value(rotated1, 9))

    rotated2 = [2, 2, 2, 3, 4, 2]
    print(find_value(rotated2, 3))
    print(find_value(rotated2, 1))

    rotated3 = [6, 7, 9, 3, 3, 3]
    print(find_value(rotated3, 7))
    print(find_value(rotated3, 5))

    rotated4 = [3, 4, 2, 2, 2, 2]
    print(find_value(rotated4, 2))
    print(find_value(rotated4, 3))
    print(find_value(rotated4, 5))