Binary Search Coded

Related: Find Minimum in Rotated Sorted Array

Todo

Code this recursively

---

Another Recursive

Recursive

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def r(l, h):
            if l == h:
                return -1
            
            mid = (l + h) // 2
 
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                return r(mid + 1, h)
            else:
                return r(l, mid)
 
        return r(0, len(nums))

Iterative

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l = 0
        h = len(nums)
 
        while l < h:
            mid = (l + h) // 2
 
            if target == nums[mid]:
                return mid
            elif target < nums[mid]:
                h = mid
            else:
                l = mid + 1
        
        return -1

Another Iterative

Caution

This would probably work if you start out with high as n - 1, rather than as n

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l = 0
        h = len(nums) - 1
 
        while l <= h:
            mid = (l + h) // 2
 
            if target == nums[mid]:
                return mid
            elif target < nums[mid]:
                h = mid - 1
            else:
                l = mid + 1
        
        return -1

Previous Attempts: Binary Search Coded 2023-02-18 15.02.15.excalidraw Binary Search Coded 2023-02-17 13.39.13.excalidraw

---

References

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