Use when you need to locate an element or boundary in a sorted array efficiently in
O(log n) time.
Use when you need to locate an element or boundary in a sorted array efficiently in O(log n) time.
Keywords for identifying Binary Search Problems
β Sorted array / sorted input
β Find target or boundary
β First / last occurrence
β Smallest / largest index that satisfies condition
β Monotonic condition (true β false or false β true)
lhs = 0 # left pointerrhs = len(nums)-1 # right pointer
"""we use lhs + 1 < rhs to ensure:- lhs pointer always stays on left side- rhs pointer always stays on right side- leave space for a mid pointer in betweenthis makes post processing stage easier to think about"""while lhs + 1 < rhs: """ we can replace "(lhs+rhs)//2" with "lhs+(rhs-lhs)//2" for languages where we have to worry about overflow like C/C++ """ mid = (lhs + rhs)//2 if nums[mid] == target: return mid elif nums[mid] < target: lhs = mid else: rhs = mid """post processing:lhs pointer should always be next to rhs pointer here eg) L Rwith 1 exception when lhs and rhs pointer are ontop of each other in an array with just 1 element"""if nums[lhs] == target: return lhselif nums[rhs] == target: return rhselse: return -1 # target not foundTry questions yourself first before looking at solution π