Binary Search(Vanilla)

Question

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Linear search Vs Binary Search?

1. To find an element in an array, we use linear search. We look at each element in the array until we find the one we are looking for. This operation has a time complexity of O(N), as we may have to look at each element before finding our value: If the element is the last one in the array and we start the search from the beginning. Binary Search allows us to find an element in a Sorted Array O(log(n)) time. How is that possible? In this chapter, we will try to understand binary search by searching for an element in a sorted array.
Copy

for i in range(len(nums)):
		guess = nums[i]
    if guess == target:
        return i
 
return -1

2. Looking for an element in linear time.

Intuition using random guesses

Let’s try picking a random number from a sorted array, it can tell us three things.

1. It might turn out the number we pick is the the one we we are looking for.
1. We have found it. Trés Bien! We simply return it.

2. If the number is smaller than the target.
1. Since the array is sorted, and we have chosen 3, we can be sure that all the elements that come before 3 are also going to be smaller than 3.

2. We can get rid of all the elements after and including 3

3. The number is larger than the target.
1. We can be sure since the array is sorted, and we chose 5. All the elements that are going to come after 5 are also going to be greater than 5.

2. We can get rid of all the elements after and including 5.

4. We can repeat this process of picking a random number multiple times to further narrow down the range. In fact, with just two comparisons, we were able to reduce the range from 6 to 1.
5. Choosing the midpoint as the random number of the array is a good practice. This is because we assume the array is randomly distributed, and selecting the midpoint gives us consistently better odds.
1. Taking shots in the dark: Imagine there are two billion possible numbers in a sorted order starting from 0. We are looking for the number at the one billionth position. We want to find the best solution quickly, so we need to make sure we don't waste our guesses. For example, if we guess the 10th number in the sequence, and the answer is at the one billionth position, we will only be able to eliminate the first 10 numbers. Guessing the numbers in the middle of the range can help us learn as much as possible with each guess. For that, we will need to keep track of the low and high ends of the range and then calculate the middle of the range.
💡
should the "midpoint" location of binary search always be at 1/2? (Answer from stack-over flow)

Implementation

1. What do the left and right pointers mean? We denote the possible range using two pointers: left (the lowest index possible) and right (the largest index possible).

2. Calculating the mid point using indexes of the array.
2. When finding the midpoint for a range with an even number of elements, we round down. For example, when there are 6 elements, and we are starting from index 0, there can be two possible midpoints.
1. 2 if we round down
2. 3 if we round up
3. We can do both, but common practice is to stick with rounding down.

3. For Odd vales we get a single mid point. One possible midpoint. For 3 elements.

4. Integer Overflow!
1. This concept should be a lesson of its own. In some languages (e.g. Java, C++), integers are of fixed size, so they might overflow when two large integers are added together. For example, if the largest number you can store is 2147483647, then in calculating the midpoint for a large array, the sum of left + right might end up being larger than 2147483647, resulting in an overflow. We don’t have to worry about that in python as python integers don’t have a set limit.
2. To counter the integer overflow we use a slightly different formula
Copy

mid = (left + right) // 2 # overflow can happen

mid = right + (left-right) //2 # to prevent overflow

3. Math

💡
Reference (overflow)
3. Narrowing the range of possible values.
1. Smaller than target: the value at the midpoint is 3, which is smaller than the target value of 4. We can disregard all elements before 3. As they are smaller than 3 and by that smaller than 4. This leaves us with half of the original array.

1. We do that by moving the left pointer = mid + 1—reducing possible range/values.

2. Code
Copy

guess = nums[mid] # querying the array for a guess value

Copy

elif guess < target:
  left = mid + 1

2. Greater than the target: the value at the midpoint is 5, larger than the target of 4. All elements after 5 will be larger than 4, so disregard them as well.

1. We do that by moving the right pointer = mid - 1 (reducing possible range)

Copy

elif guess > target:
  right = mid - 1

3. In two iterations, we checked for five elements, saving three comparisons. With larger arrays, we can save exponentially more comparisons.
4. If the midpoint is equal to the target, we simply return the midpoint. This can happen at any comparison during the search, and in this case, the last element left was the target.

Copy

if guess == target:
    return mid

4. Index vs in the number: we are returning the index of the midpoint instead of the value.
5. When do we terminate?
1. We terminate either when we find the value and return it, or when the left and right overlap and we conclude that the element we were looking for doesn't exist in the array.
1. For example, if we were looking for 3.5, and happens to be less than 4 or midpoint, we would have to move the right = mid + 1 right and left will overlap: this means that the search space has been fully exhausted.

2. We know we didn't find the element we were looking for and have exhausted the range, so we simply return -1. We can do this using a while loop.
Copy

while left <= right: 
	# range has not overlapped
	 
	# binary search code here
	      
# not found :(
return -1

Code

class Solution:
    def search(self, nums,target):
        
        left,right = 0, len(nums)-1
        
        
        while left <= right:
            
            mid = right + (left-right) //2
            guess = nums[mid]
        
            #Target found 
                #return immediately
            if guess == target:
                return mid
       
            # Target on the right Side
            # move left pointer toward the right

            elif guess < target:
                left = mid + 1
            
            # Target on the left Side
                # move right pointer toward the left
            
            elif guess > target:
                right = mid - 1
    
        # not found :(
        return -1

Sandbox—PythonTutor (Visualized)

Complexities

Time Complexity: O(log(n))

Space Complexity: O(1)

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

Follow-ups

1. Will binary search work if the order is reversed?
1. With a minor change YES
💡
Order Agnostic Binary Search
2. Will binary search work if there are negative numbers in an array?
1. Yes the ascending order still remains consistent in integers [-4,-3…5,6,7]
3. Will binary search work if there are duplicate values in the array?
1. Yes, it will still work, as the array's order remains unchanged even with duplicate values, though you might have many indexes having the same values.
1. If there are multiple values for each element so you might get the first, last, or any mid-index of that value we deal with these questions further in 🕧First and last occurrence of an Element in a Sorted Array .
4. Can you do a Binary search recursively?

💡
Yes: Binary Search Using Recursion