Binary Search Variant

Binary search is a highly efficient algorithm for finding an item from a sorted list of items. It starts by comparing the middle item of the array. If the target value matches the middle item, its position in the array is returned. If the target value is less or more than the middle item, the search continues on the lower or upper half of the array, respectively, eliminating the other half. Here are some LeetCode problems that can be solved using a binary search variant:

1. Standard Binary Search: Find an element in a sorted array.

   • Binary Search

2. Binary Search for the First or Last Position of an Element: If an array contains duplicates, and you need to find the position of the first or last occurrence of an element.

   • Find First and Last Position of Element in Sorted Array

3. Binary Search with Rotated Array: If the array has been rotated, a modified binary search can still find an element.

   • Search in Rotated Sorted Array

4. Binary Search in 2D matrix: Elements are sorted both row-wise and column-wise.

   • Search a 2D Matrix

5. Binary Search to Compute Square Root or Other Mathematical Computations: Binary search can be used to perform some mathematical calculations to a certain precision.

   • Sqrt(x)
   • Capacity To Ship Packages Within D Days

6. Search in a Nearly Sorted Array: In a nearly sorted array, each element is almost at its correct position, but can be away by at most k positions.

   • This specific problem is not found on LeetCode, but is a classic variation of binary search.

Remember, there may be multiple solutions to a problem, and the choice of algorithm depends on the specific constraints and requirements of the problem.

The Binary Search algorithm is an efficient way to find a specific target in a sorted collection. However, it is often used in a variant manner to solve different types of problems.

One common variant is the lower bound or upper bound binary search. It is often used to find the first or last occurrence of a target in a sorted array, or to find the position where a target should be inserted to maintain the sorted order of an array. An example LeetCode problem is “Find First and Last Position of Element in Sorted Array” (LeetCode 34).

Here is a Python code for the lower bound binary search variant:

1
2
3
4
5
6
7
8
9

def lower_bound(nums, target):
    left, right = 0, len(nums)
    while left < right:
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

In this code, lower_bound function returns the index of the first element that is not less than the target. The search range is narrowed down in each iteration by moving the left or right pointer based on the comparison between nums[mid] and target. If nums[mid] is less than target, left is moved to mid + 1 to exclude all numbers that are less than target. Otherwise, right is moved to mid to exclude numbers that are not less than target. The loop continues until left is no longer less than right, at which point left is the index of the first element that is not less than target. If no such element exists, left will be len(nums).