DEV Community

Cover image for Binary Search in Python
Wint Khant Lin
Wint Khant Lin

Posted on • Updated on

Binary Search in Python

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
Enter fullscreen mode Exit fullscreen mode

Explanation With Image

Image description

Top comments (0)