Binary Search
Statement
There’s an array of integers numbers, sorted in ascending order, and an integer target. If target exists in the array, then return its index, otherwise return -1.
Constraints
- 1 ≤
numbers.length()≤ 10³ - -10⁴ ≤
numbers[i],target≤ 10⁴ numbers[i]is unique
Solution
"""
production algorithm
"""
class Solution:
def binary_search(self, nums, target):
"""
time complexity O(logn)
space complexity O(1)
"""
low, high = 0, len(nums) - 1
while low <= high:
mid = (high + low) // 2
if nums[mid] == target:
return mid
if target < nums[mid]:
high = mid - 1
else:
low = mid + 1
return -1"""
unit tests
"""
from unittest import TestCase
from algorithms.modified_binary_search.binary_search.solution import Solution
class SolutionTestCase(TestCase):
def test_target_is_first_middle(self):
# Given
numbers = [1, 3, 4, 8, 9, 10, 11, 12, 13, 15,
16, 17, 18, 20, 21, 22, 23, 25, 26, 29]
target = 16
solution = Solution()
# When
actual = solution.binary_search(numbers, target)
# Then
expected = 10
self.assertEqual(actual, expected)
def test_target_is_left_of_first_middle(self):
# Given
numbers = [1, 3, 4, 8, 9, 10, 11, 12, 13, 15,
16, 17, 18, 20, 21, 22, 23, 25, 26, 29]
target = 15
solution = Solution()
# When
actual = solution.binary_search(numbers, target)
# Then
expected = 9
self.assertEqual(actual, expected)
def test_target_is_right_of_first_middle(self):
# Given
numbers = [1, 3, 4, 8, 9, 10, 11, 12, 13, 15,
16, 17, 18, 20, 21, 22, 23, 25, 26, 29]
target = 17
solution = Solution()
# When
actual = solution.binary_search(numbers, target)
# Then
expected = 11
self.assertEqual(actual, expected)
def test_target_is_start(self):
# Given
numbers = [1, 3, 4, 8, 9, 10, 11, 12, 13, 15,
16, 17, 18, 20, 21, 22, 23, 25, 26, 29]
target = 1
solution = Solution()
# When
actual = solution.binary_search(numbers, target)
# Then
expected = 0
self.assertEqual(actual, expected)
def test_target_is_end(self):
# Given
numbers = [1, 3, 4, 8, 9, 10, 11, 12, 13, 15,
16, 17, 18, 20, 21, 22, 23, 25, 26, 29]
target = 29
solution = Solution()
# When
actual = solution.binary_search(numbers, target)
# Then
expected = 19
self.assertEqual(actual, expected)
def test_target_nonexistent(self):
# Given
numbers = [1, 3, 4, 8, 9, 10, 11, 12, 13, 15,
16, 17, 18, 20, 21, 22, 23, 25, 26, 29]
target = 55
solution = Solution()
# When
actual = solution.binary_search(numbers, target)
# Then
expected = -1
self.assertEqual(actual, expected)Strategy
Modified Binary Search.
Explanation
Initialize low and high pointers as the low and high indexes of the array. Then while low is less than or equal to high, calculate the middle index between them. Then there’s three cases.
If the target integer is at the middle index, then return the middle index. Otherwise, if the target integer is left of the middle index, then set high as the middle index minus one, and search the left subarray. Finally, if the target integer is right of the middle index, then set low as the middle index plus one, and search the right subarray.
If target doesn’t exist in the array, i.e. low and high pass each other such that high < low and so a subarray cannot exist, then return -1.
Time Complexity
The middle of a subarray can be calculated a maximum of logn times, where n is the size of the input array. That’s because the array can be divided in half a maximum of logn times, before there are no further subarrays, i.e. when high becomes less than low. Therefore, the time complexity of the algorithm is O(logn).
Space Complexity
The algorithm only uses constant auxiliary space to find the target integer index. Therefore, the auxiliary space complexity of the algorithm is O(1).
