Binary search is a search algorithm that finds the position of a target value within a sorted array. It works by repeatedly dividing in half the portion of the list that could contain the item, until you’ve narrowed down the possible locations to just one. This algorithm has a time complexity of O(log N) which makes it very efficient for large datasets.
def search(self, nums: list, target):
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif target < nums[mid]:
right = mid - 1
else:
left = mid + 1
return -1
search([-50, -40, -30, -20, -10, 0, 10, 20, 30, 40, 50], 20) # Output 7
Top comments (0)