Given a sorted (in ascending order) integer array nums
of n
elements and a target
value, write a function to search target
in nums
. If target
exists, then return its index, otherwise return -1
.
Example 1:
Input:nums
= [-1,0,3,5,9,12],target
= 9 Output: 4 Explanation: 9 exists innums
and its index is 4
Example 2:
Input:nums
= [-1,0,3,5,9,12],target
= 2 Output: -1 Explanation: 2 does not exist innums
so return -1
Note:
nums
are unique.n
will be in the range [1, 10000]
.nums
will be in the range [-9999, 9999]
.Source
def binary_search(nums, target):
"""Iterative implementation of binary search"""
left = 0
right = len(nums)-1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
left = mid+1
if target < nums[mid]:
right = mid-1
return -1
def binary_search(nums, target):
"""Alternative version of above solution"""
left = 0
right = len(nums) # vs. len(nums)-1
while left < right: # vs. <=
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
left = mid+1
if target < nums[mid]:
right = mid # vs. mid-1
return -1
nums = [-1,0,3,5,9,12]
target = 9
binary_search(nums, target)
4
nums = [-1,0,3,5,9,12]
target = 2
binary_search(nums, target)
-1
Solve it both iteratively and recursively. Solve it using built-in methods too.
def binary_search(nums, target):
"""Recursive implementation of binary search"""
def helper(left, right):
if right < left: # base case: target not present
return -1
nonlocal nums, target
mid = left + (right-left)//2
if nums[mid] == target: # base case: target at middle index
return mid
if target > nums[mid]:
return helper(mid+1, right)
else:
return helper(left, mid-1)
return helper(0, len(nums)-1)
def binary_search(nums, target):
"""Using Built-in method index()"""
try:
return nums.index(target)
except ValueError: # index() returns an error if target is not in nums
return -1
from bisect import bisect_left
def binary_search(nums, target):
"""Using Built-in method bisect_left()"""
i = bisect_left(nums, target)
return i if i != len(nums) and nums[i] == target else -1