Skip to main content

Binary Search


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



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
end = mid-1
return -1