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:
[-5, 1, 3, 6, 7, 9], target = 3
Example output:
2

Solution

def find_target(arr, target):
    # Binary search
    # O(log n)
    # The array is sorted, so we can use binary search to find the target.
    # Binary search is O(log n) because we divide the array in half each time.
    # If the array is not sorted, we would have to use a linear search, which is O(n).
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

print(find_target([-5, 1, 3, 6, 7, 9], 3))