First and last occurrence of an Element in a Sorted Array

Prerequisites: 🍦Binary Search(Vanilla) , 🔑Find the First True in a Sorted Boolean Array

Question

nums = [1,2,4,4,4,5,6]
output = [2,4]
There are 3 instances of the element 4 in the array. First one at index 2 and last one at index 4.

First Element: Intuition + implementation

1. Since we have duplicates, 🍦Binary Search(Vanilla) will give us a value, but may not provide the index of the first duplicate value.
2. We know that the first element in a set of duplicates will be the leftmost. Therefore, if we find an element, we can't be sure it is the leftmost. Instead of returning it, we should store it as a possible first and keep the search space to the left open, in hope of finding another similar target.
Copy

guess = nums[mid]
if guess == target:
    first = mid
    right = mid - 1 # Chop elements to the right

3. The rest of the code has the same functionality as regular binary search. Simple as that!
Copy

def searchFirst(nums, target) : 
    
    left,right = 0,len(nums)-1
    first = -1

    #edge case nums = [] target = 0
    if len(nums) < 1:
        return -1
    
    left,right = 0,len(nums)-1
    while left <= right:
    
        mid = left + (right-left)//2
    
        
        guess = nums[mid]
				
				if guess == target:
            first = mid
            right = mid - 1
            
        elif guess < target:
             left = mid + 1
            
        elif guess > target:
            right = mid - 1
                
            
            
    # Element not in the array
    return first if nums[first] == target else -1

First Element: Intuition 2.0 The story of two halves ⭐

1. We can use the technique mentioned before to easily find a solution. However, as discussed in the article 🍫Binary search Vanilla to Chocolate , we will use this question to gain a better understanding of how to divide the array into two halves to find the target.

array = [1,2,4,4,4,5,6] target = 4


2. In this case, how can a decision bring us closer to the target?
1. The lower half of the array (elements 1 and 2) indicates that target 4 is to the right. The upper half (elements 5 and 6) indicates that the target is to the left—facilitated by the sortedness of the array.

3. The duplicates (index 3 and 4) also fall in the upper half of the array; the target (the leftmost 4) is to their right.

1. All values need to have a half, as we are attacking the problem from a binary decision; moving closer to the target(first four). This leaves us with an interesting problem: where do the first 4 go? I previously said that the target is to the left of all elements in the upper half. If we include the first 4 in the upper half, that would contradict that since the leftmost 4 is the target. Let's see how that plays out when the first 4 is included in the upper half.
2. Algorithm: Pick a midpoint, and check its element; if found in upper half, remove all to its right; if found in lower half, remove all to its left, including itself. We hop between each half chopping elements and reducing the range.

3. I am making a case that the last element we will cut from the upper half will be our target.
1. Every time we end up on an element in the upper half, we remove the elements to its right, including itself.
2. We can only remove elements to the right, so we can only remove the last most element, when we are on it, once we remove that we will never enter the upper half again.
3. We never remove elements from the lower half when we are in the upper half.
4. Every time we are in the upper half, we will store the value as a possible leftmost value(target). Since we are cutting from the right and will not visit any element twice, with every iteration we will have the most up-to-date left-most value in the upper half. Once we cut the last element we will have our target.

5. Why is putting 4 in the lower half a problem? When we randomly end up on any 4, we are not sure which half that 4 belongs to as there are 4s in both halves, so it is difficult to write that in logic.

6. If we add the first 4 to the upper half, every binary decision will lead us to the leftmost value in the upper half. Reducing the problem to 🔑Find the First True in a Sorted Boolean Array

 def searchFirst(self, nums: List[int], target: int) -> int: 
    
        left,right = 0,len(nums)-1
        first = -1

     
        if len(nums) < 1: #edge case:nums = [] target = 0
            return -1
        
        
        while left <= right:
            
            mid = left + (right-left)//2
            
    
            guess = nums[mid]
            
            if guess >= target: #upper half move to the left
                first = mid
                right = mid - 1
            
                    
            else: # False
                left = mid + 1
                
                
                
        # if Element not in the array
        return first if nums[first] == target else -1

def searchFirst(nums, target) : 
    
    left,right = 0,len(nums)-1
    first = -1

    #edge case nums = [] target = 0
    if len(nums) < 1:
        return -1
    
    left,right = 0,len(nums)-1
    while left <= right:
    
        mid = left + (right-left)//2
    
        
        guess = nums[mid]
				
				if guess == target: #upper half move to the left
            first = mid
            right = mid - 1
            
        elif guess < target:
             left = mid + 1
  
        elif guess > target: #upper half move to the left
            right = mid - 1
                
            
            
    # Element not in the array
    return first if nums[first] == target else -1

Last Element: Intuition + implementation

1. We can use a slight alteration to the binary search we used to find the first instance of 4. Instead of cutting from the right, we cut from the left by moving the left pointer. This returns the last value of 4, which is what we end up on. Easy enough. But let's use the previous insights to solve this problem.
Copy

if target == nums[mid]:
    last = mid
    left = mid + 1 # increasing

2. We reduced finding the first element to 🔑Find the First True in a Sorted Boolean Array . What did we learn from that?
3. In the previous part, we found out that the search always optimizes towards the edge elements in the right half (this will also be true for the left half): rightmost in lower, leftmost in upper—as these are the last element we cut in our bid to find the target. How can we reframe the problem that the last duplicate(4 in this case) happens to be the edge element in either half?

4. We can change what is considered true and include all the duplicates in the lower half. Returning the edge value in the lower half as our last duplicate (i.e. last false in this case which is different from the first True).

Code

def searchLast(self, nums: List[int], target: int) -> int:
            
            
        if len(nums) < 1: #edge case:nums = [] target = 0
            return -1

        left,right = 0,len(nums)-1
        last = -1
        
        while left <= right:

            mid = left + (right-left)//2

            guess = nums[mid]

            if guess > target:
                right = mid - 1

            
            
            else: # False : Possible Value			
                last = mid
                left = mid + 1


        return last if nums[last] == target else -1

Last True from the left instead of from the right.

1. Although the answer is correct in the last part, it seems strange to return a false value as a possible last. How can we change this? We can redefine which half counts as true,( saving a possible value in that half and returning it at the end). This is the beauty and flexibility of thinking about binary search in terms of halves and returning an edge value. It is up to you to decide how to reframe the problem. Let's now optimize the last true value from the left.

Implementation: First + last

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:

        first, last = self.searchFirst(nums,target),self.searchLast(nums,target)
        return[first,last]
        
    def searchFirst(self, nums: List[int], target: int) -> int: 
    
        left,right = 0,len(nums)-1
        first = -1

     
        if len(nums) < 1: #edge case:nums = [] target = 0
            return -1
        
        
        while left <= right:
            
            mid = left + (right-left)//2
            
    
            guess = nums[mid]
            
            if guess >= target: #upper half move to the left
                first = mid
                right = mid - 1
            
                    
            else: # False
                left = mid + 1
                
                
                
        # if Element not in the array
        return first if nums[first] == target else -1
                

        
    def searchLast(self, nums: List[int], target: int) -> int:
            
            
        if len(nums) < 1: #edge case:nums = [] target = 0
            return -1

        left,right = 0,len(nums)-1
        last = -1
        
        while left <= right:

            mid = left + (right-left)//2

            guess = nums[mid]

            if guess > target:
                right = mid - 1

            
            
            else: # False : Possible Value			
                last = mid
                left = mid + 1


        return last if nums[last] == target else -1

SandBox PythonTutor (Visualized)

Conclusion

Through this question we understood,

1. Make a binary decision by dividing it into two halves and going left or right to find the target.
2. Choosing which elements fall into which halves, what constitutes to be a True or False
3. How the binary search optimizes edge values for each half.
4. Flexibility in terms of what half constitutes a True.

Now you have a much-needed understanding of how to think about Binary search and reframe complex problems to halves and move closer to the targets

Complexities

Time Complexity: O(log(n))

Space Complexity: O(1)

📐Understanding Time Complexity of OLog(N): Math + Intuition