binary_search

Solution

	
	"""
https://leetcode.com/problems/binary-search/description/

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.
"""

from typing import List


def binary_search(nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + ((right - left) // 2)
        guess = nums[mid]
        if guess > target:
            right = mid - 1
        elif guess < target:
            left = mid + 1
        else:
            return mid
    return -1

	

Tests

	
	from publicmatt.leet.problems.binary_search import binary_search


def test_small():
    nums = [1, 2, 3, 4, 5]
    target = 3
    assert binary_search(nums, target) == 2


def test_not_there():
    nums = [1, 2, 3, 4, 5]
    target = 6
    assert binary_search(nums, target) == -1


def test_with_negatives():
    nums = [-1, 0, 3, 5, 9, 12]
    target = 9
    assert binary_search(nums, target) == 4, "9 exists in nums and its index is 4"


def test_another_non_exists():
    nums = [-1, 0, 3, 5, 9, 12]
    target = 2
    assert binary_search(nums, target) == -1, "2 does not exist in nums so return -1"