Problem

Given a sorted array of integers, write a function that returns the index of the target value if it exists in the array, or -1 if it does not.
Example input: [0, 1, 2, 3, 4, 5, 6], 4
Example output: 4

Solution

def find_index(array, target):
    # Binary search is the optimal solution for this problem.
    # It is optimal because it is O(log n) time complexity.
    # This is because the array is sorted and we can use the
    # divide and conquer approach to find the target value.
    # We can do this by finding the midpoint of the array and
    # comparing the target value to the value at the midpoint.
    # If the target value is less than the value at the midpoint,
    # we can search the left half of the array. If the target value
    # is greater than the value at the midpoint, we can search the
    # right half of the array. We can repeat this process until we
    # find the target value or until we have searched the entire array.
    # If we have searched the entire array and have not found the target
    # value, we can return -1.
    left = 0
    right = len(array) - 1
    while left <= right:
        mid = (left + right) // 2
        if array[mid] == target: return mid
        elif array[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

print(find_index([0, 1, 2, 3, 4, 5, 6], 4))