binarySearch.py

# Binary Search (Edge case: i/p: [1] o/p: [0,0])
class Solution:
    def searchRange(nums, target):
        left = searchLeft(nums, target, 0, len(nums)-1)
        if left < 0:
            return [-1, -1]
        else:
            right = searchRight(nums, target, left, len(nums)-1)
            return [left, right]
        
def searchLeft(nums, target, lo, hi):
    while lo <= hi:
        mid = (lo+hi) // 2
        if nums[mid] == target and (mid == 0 or nums[mid-1] != target):
            return mid
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1
                
def searchRight( nums, target, lo, hi):
    while lo <= hi:
        mid = (lo+hi) // 2
        if nums[mid] == target and (mid == len(nums)-1 or nums[mid+1] != target):
            return mid
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1

 # BETTER SOLUTION:

def searchRange(nums, target):
        index = searchIndex(nums, target, 0, len(nums)-1)
        if index == -1:
            return [-1, -1]
        l = r = index
        while l >= 0 and nums[l] == target:
            l -= 1
        while r < len(nums) and nums[r] == target:
            r += 1
        return [l+1, r-1]
                
def searchIndex(nums, target, lo, hi):
    while lo <= hi:
        mid = (lo+hi) // 2
        if nums[mid] == target:
            if mid == len(nums)-1 or nums[mid+1] != target:
                return mid
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

nums = [5,7,7,8,8,10]
target = 8
print(searchRange(nums, target))

# Find a minimum in a Rotated Array

def findMin(arr):
    lo, hi = 0, len(arr)-1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1
        else:
            hi = mid        
        return nums[lo]
nums = [4,5,6,7,0,1,2]
print(findMin(nums))

# Find target in rotated array with duplicates
class Solution:
    def search(self, arr: List[int], target: int) -> bool:
        lo = 0
        hi = len(arr) - 1
        while (lo <= hi):
            mid = (lo + hi) // 2
            if arr[mid] == target:
                return True
            while (lo != mid and arr[mid] ==arr[lo]):
                lo += 1
            if arr[lo] > arr[mid]:
                if target >= arr[lo] or target <=arr[mid]:
                    hi = mid - 1
                else:
                    lo = mid + 1
            else:
                if target > arr[mid]:
                    lo = mid + 1
                else:
                    hi = mid - 1
            return False