Find the minimum difference element in a sorted array

Prerequisites : 🍦Binary Search(Vanilla) , 🔑Find the First True in a Sorted Boolean Array , 🎢Floor (Lower Bound) , 🛖Ceiling(Upper Bound)

Question

Input: [2, 5, 10, 12, 15], target = 6
Output: 5
Explanation: The difference between the target value '6' and '5' is the minimum.

Input: a[] = [2, 5, 10, 12, 15], target = 5
Output: 5

Intuition

1. If the target does not exist, which elements in a sorted array are closest to the target? Consider this question.
1. The elements on either side of the target's possible location? Yes.
2. Input: [2, 5, 10, 12, 15], target = 6
3. Between 5 and 10 what will be the closest to target 6.
2. Have we done a question before that gives us access to these same values?
1. 🛖Ceiling(Upper Bound)
2. 🎢Floor (Lower Bound)
3. In order to calculate the min difference with the target from the target value, we simply get the floor value and the ceiling value and get the minimum among them. Simple enough.
1. Input: [2, 5, 10, 12, 15], target = 6
1. Floor is 5, ceil is 10
2. The minimum is min (abs(6-5) , abs(6-10))
4. If the target exists in the array. The floor/ceil is equal to the target.
1. [2, 5, 10, 12, 15], target = 5
1. abs(5-5) = 0

Binary Search coming full circle

1. How does binary search work? We move the right pointer toward the left and the left pointer toward the right in an attempt to find the target.

2. When we don’t find the target, the right and left intersect, and cross each that is when the search is exhausted and the loop ends.
3. Let's go over the whole steps, instead of 4 we are looking for 3.5 that doesn’t exists what will be its upper bound and lower bound in the array.
1. 3 is lower bound
2. 4 is upper bound
4. Dry run!
1. Step 1, left moves towards the right as 3(mid)is less than 3.5.

2. Step 2, the right moves towards the left as 5(mid) is greater than 3.5, hence the overlap.

3. Step 3, the right moves towards the left as 4(mid) is greater than 3.5, hence passing each other.

4. The conclusion.
1. The left pointer and right pointer overlap and pass each other, the left ends up at the upper Bound (ceiling) and the right ends up at the lower bound(Floor).

2. Can there be a case where the right is the ceil and left is the floor? No, If the target doesn’t exist they will have to pass each other. Left will end up at a higher index than the right hence. That will not be possible. Proof of contradiction

#mindBlown #BinarySearchComingFullCircle

Take aways

Why did we talk about this? This kind of thinking helps us understand how binary search works. We move the pointers towards the target: the right pointer moves leftwards and the left pointer moves rightwards. We keep reducing the range as we get closer to the target. If the target is not found, the pointers end up at the values closest to the target. That is how binary search works and is the engine of logarithmic search. How the possible value is the last place either the left pointer or right pointer was, depending on if we are looking for upper bound and lower bounds.pheaps

Complexities

Time Complexity: O(log(n))

Space Complexity: O(1)

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

Bouns Problem

1. Lets take it further and solve and try to solving the the same problem 🎏Search Insert Position(Sorted Array) Upper Bound with Binary search.
2. The problem is reduced to finding the upper bound. In Binary search if the target is found that is the upper bound if not found the left and right pointer will end up to the values closest to the target. We are looking for the upper bound so we can simply return the left pointer’s value.

class Solution:

    def searchInsert(self, nums,target):

        left, right = 0, len(nums) - 1
   

        while left <= right:

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

            if nums[mid] == target:
                return mid

            elif nums[mid] > target:
                right = mid - 1
						
		 
            else: # target > nums[mid]
                left = mid + 1

	      # if not found the left pointer will go out of range, 
				# that is our insert point
        return left

class Solution:
    def search(self, nums,target):
        
        left,right = 0, len(nums)-1
        
        


        while left <= right:
            mid = right + (left-right) //2
            guess = nums[mid]
      
						if guess == target:
                return mid
            
            elif guess > target:
                right = mid - 1

						
						elif guess < target:
                left = mid + 1
    
        # not found :(
        return -1

3. When searching for the number seven, if it exists on either end, the left and right pointers will converge at index 3 and end the loop, giving us the answer. The same applies in reverse for the right pointer meeting at the opposite end.
Copy

nums = [1,3,5,6] target = 7

[1,3,5,6]
 l --> r 

[1,3,5,6]
       r
			 l--> loop ends 

Return ceil/insertPoint as left pointer
For something like this, the left pointer will meet the right at index 3 and in search for seven will move further right, this will end up terminating the loop and will give us our answer.

nums = [1,3,5,6] target = 0

	[1,3,5,6]
	 l <-- r 
	
	[1,3,5,6]
	 l
<--r loop ends 

Return ceil/insertPoint as left pointer

SandBox PythonTutor (Visualized)

Complexities

Time Complexity: O(log(n))

Space Complexity: O(1)

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

Compared to 🎏Search Insert Position(Sorted Array) Upper Bound we save a little more space as we are not using an extra value with the variable of ceil. We are simply returning the pointers. The space complexity remains the same theoretically, but in an applied sense, it changes slightly.