Prerequsites : Binary Search(Vanilla) , Find the First True in a Sorted Boolean Array
Implementation
Instead of simply doing Binary Search, we will be combining Binary Search(Vanilla) and Find the First True in a Sorted Boolean Array to find an element in a sorted Array.
- Divide the array into two halves: one where all values in that half are greater than or equal to the target (true), and one where all values are less than the target (false).
- The target we are looking for will be the first value in the True half.
- Since the target will be the first value in the true half. The problem is reduced to Find the First True in a Sorted Boolean Array
Code for Find the First True in a Sorted Boolean Array
class Solution:
def firstTrue(self, bools):
(left, right) = (0, len(bools) - 1)
possibleValue = -1
while left <= right:
mid = left + (right - left) // 2
# True
if bools[mid]:
possibleValue = mid
right = mid - 1
# False
else:
left = mid + 1
return possibleValueCode Binary Search Chocolate
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0,len(nums)-1
possibleValue = -1
while left <= right:
mid = left + (right-left)//2
# true value
if nums[mid] >= target: #change
possibleValue = mid
right = mid - 1
else:
left = mid + 1
# possibleValue greater than target (might not be target)
return possibleValue if nums[possibleValue] == target else -1 #changeCode Binary Search(Vanilla)
class Solution:
def search(self, nums,target):
left,right = 0, len(nums)-1
while left <= right:
mid = right + (left-right) //2
if target == nums[mid]:
return mid
elif target > nums[mid]:
left = mid + 1
elif target < nums[mid]:
right = mid - 1
# not found :(
return -1Code Binary Search Chocolate
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0,len(nums)-1
possibleValue = -1
while left <= right:
mid = left + (right-left)//2
# true value
if nums[mid] >= target: #change
possibleValue = mid
right = mid - 1
else:
left = mid + 1
# possibleValue greater than target (might not be target)
return possibleValue if nums[possibleValue] == target else -1 #changeSandBox PythonTutor (Visualized)
Complexities
Time Complexity: O(log(n))
Space Complexity: O(1)
Understanding Time Complexity of OLog(N): Math + Intuition
Further analysis:
The complexity of the chocolate method is theoretically the same, but its efficiency in implementation can vary depending on the array. It increases when there are fewer if conditions being checked, but decreases when the loop doesn't terminate until the range is exhausted, instead of returning as soon as the element is found. It does, however, increase a little in terms of space, as the variable possibleValue is stored but that is only constant time :)