Constant Time
Constant Time
/Binary Search
Binary Search
/
🍫
Binary search Vanilla to Chocolate
🍫

Binary search Vanilla to Chocolate

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.

  1. 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).
    1. The target we are looking for will be the first value in the True half.
  2. 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
    3. image

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 possibleValue

Code Binary Search Chocolate

Code 🍦Binary Search(Vanilla)

Code Binary Search Chocolate

SandBox 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 :)

Further Understanding

Using the Alternate Binary Search Approach (Optional)
Logo
YouTubeDiscord
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 #change
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 -1
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 #change