binary_search
1# @leet start 2class Solution: 3 def search(self, nums: list[int], target: int) -> int: 4 """ 5 A classic iterative binary search algorithm. 6 This starts out by setting two pointers to the ends of the array 7 and finding the midpoint between them. 8 Since python has biginteger promotion, we calculate the mid with (l + r) // 2. 9 In a language with fixed-width integers, this can overflow, so (r - l) // 2 + l 10 also works. 11 12 So in a loop: 13 If the mid is equal to the target, return the midpoint. 14 If the midpoint is less than the target, then set the left to mid + 1. 15 Otherwise, the midpoint is greater than the target, set right to mid - 1. 16 17 This finds the number in $O(log{}n)$ time or exits the loop, at which point 18 the function returns -1. 19 """ 20 left, right = 0, len(nums) - 1 21 while left <= right: 22 mid = (left + right) // 2 23 if nums[mid] == target: 24 return mid 25 elif nums[mid] < target: 26 left = mid + 1 27 else: 28 right = mid - 1 29 return -1 30 31 32# @leet end 33 34 35def test(): 36 assert 2 + 2 == 4
class
Solution:
3class Solution: 4 def search(self, nums: list[int], target: int) -> int: 5 """ 6 A classic iterative binary search algorithm. 7 This starts out by setting two pointers to the ends of the array 8 and finding the midpoint between them. 9 Since python has biginteger promotion, we calculate the mid with (l + r) // 2. 10 In a language with fixed-width integers, this can overflow, so (r - l) // 2 + l 11 also works. 12 13 So in a loop: 14 If the mid is equal to the target, return the midpoint. 15 If the midpoint is less than the target, then set the left to mid + 1. 16 Otherwise, the midpoint is greater than the target, set right to mid - 1. 17 18 This finds the number in $O(log{}n)$ time or exits the loop, at which point 19 the function returns -1. 20 """ 21 left, right = 0, len(nums) - 1 22 while left <= right: 23 mid = (left + right) // 2 24 if nums[mid] == target: 25 return mid 26 elif nums[mid] < target: 27 left = mid + 1 28 else: 29 right = mid - 1 30 return -1
def
search(self, nums: list[int], target: int) -> int:
4 def search(self, nums: list[int], target: int) -> int: 5 """ 6 A classic iterative binary search algorithm. 7 This starts out by setting two pointers to the ends of the array 8 and finding the midpoint between them. 9 Since python has biginteger promotion, we calculate the mid with (l + r) // 2. 10 In a language with fixed-width integers, this can overflow, so (r - l) // 2 + l 11 also works. 12 13 So in a loop: 14 If the mid is equal to the target, return the midpoint. 15 If the midpoint is less than the target, then set the left to mid + 1. 16 Otherwise, the midpoint is greater than the target, set right to mid - 1. 17 18 This finds the number in $O(log{}n)$ time or exits the loop, at which point 19 the function returns -1. 20 """ 21 left, right = 0, len(nums) - 1 22 while left <= right: 23 mid = (left + right) // 2 24 if nums[mid] == target: 25 return mid 26 elif nums[mid] < target: 27 left = mid + 1 28 else: 29 right = mid - 1 30 return -1
A classic iterative binary search algorithm. This starts out by setting two pointers to the ends of the array and finding the midpoint between them. Since python has biginteger promotion, we calculate the mid with (l + r) // 2. In a language with fixed-width integers, this can overflow, so (r - l) // 2 + l also works.
So in a loop: If the mid is equal to the target, return the midpoint. If the midpoint is less than the target, then set the left to mid + 1. Otherwise, the midpoint is greater than the target, set right to mid - 1.
This finds the number in $O(log{}n)$ time or exits the loop, at which point the function returns -1.
def
test():