Binary Search

Binary Search is an algorithm that repeatedly divides the search space in half. This searching technique follows the divide and conquer strategy. The search space always reduces to half in every iteration.resulting in a time complexity of O(log(n)), where n is the number of elements.

Condition: Array should be sorted but they can also be applied on monotonic functions where we need to find the monotonically increasing or decreasing.

It works when we need to narrow down the search space in logarithmic time.

We use two pointers, left and right. Take the average of left and right to find the mid element.

Now, we check where we should move our left and right pointers based on the condition.

Mainly, three steps are required to solve a problem:

1. Pre-processing: Sort the input if it is not sorted.
2. Binary Search: Use two pointers and find the mid to divide the search space, then choose the correct half accordingly.
3. Post-processing: Determine the output.

Advantages of Binary Search Algorithm - Binary search is faster than linear search for large data because it cuts the array in half each time, instead of checking each element one by one. This makes it quicker and more efficient.

Limitations: Binary search only works on sorted arrays, so it's not efficient for small unsorted arrays because sorting takes extra time. It also doesn't work as well as linear search for small, in-memory searches.

Applications: It is used to search element in a sorted array with O(log(n)) time complexity and it can also be used to find the smallest or largest element in the array.

Basic Binary Search Code -

Code

def binarySearch(nums, target):
    if len(nums) == 0:
        return -1

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

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

    # End Condition: left > right
    return -1

33. Search in Rotated Sorted Array
Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:
Input: nums = [1], target = 0
Output: -1

Code

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

        while left <= right:

            mid = (left + right)//2
            print(f'left is {left},right is {right} and mid is {mid}')
            if nums[mid]==target:
                return mid

            if nums[mid] >= nums[left]:
                # if nums[mid]< target and target >= nums[left]:
                if nums[left] <= target < nums[mid]:
                    right = mid -1
                else:
                    left = mid +1
            else:
                # if nums[mid] < target and target <= nums[right]:
                if nums[mid] < target <= nums[right]:
                    left = mid +1
                else:
                    right = mid - 1

        return -1

1. Use two pointers, left and right, and iterate until they overlap.
2. Find the mid element.
3. Since the array is sorted but rotated, we can’t simply compare the left or right elements with the mid.
4. First, determine which part left or right is sorted by comparing the mid pointer with the left or right pointer.
5. Based on this conclusion, adjust the pointers accordingly.

Time Complexity - O(log(n)) as the search space is getting divided into half in each iteration.
Space Complexity - O(1)

Monotonically Increasing

162. Find Peak Element

A peak element is an element that is strictly greater than its neighbors.
Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.
You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.
You must write an algorithm that runs in O(log n) time.

Example 1:
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
Example 2:
Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

Code

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) -1
        while left <= right:
            mid = (left+right)//2

            if mid >0 and nums[mid] < nums[mid-1]:
                right = mid -1
            elif mid < len(nums)-1 and  nums[mid] < nums[mid+1]:
                left = mid+1
            else:
                return mid

1. In this type of problem, we need to check for the peak by comparing the left or right element of the mid.
2. This helps determine whether the graph is trending upward or downward.
3. To find the maximum, search the upward slope and explore the right subspace.
4. To find the minimum, search the left subspace

Time Complexity - O(log(n)) as the search space is getting divided into half in each iteration.
Space Complexity - O(1)