Binary Search

Question

Given a sorted array of distinct integers, find the index of a target value using a Binary Search algorithm.

Example 1

Given an array of sorted integers nums and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

Example 1:

Input: nums = [1,3,5,6], target = 5
Output: 2

Solution

▭

all//Binary Search.py

def binary_search(arr, x):
    start = 0
    end = len(arr)-1
    while start <= end:
        mid = (start+end)//2
        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            start = mid+1
        else:
            end = mid-1
    return -1

▯

all//Binary Search.py

def binary_search(arr, x):
    start = 0
    end = len(arr)-1
    while start <= end:
        mid = (start+end)//2
        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            start = mid+1
        else:
            end = mid-1
    return -1