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:
Standard Binary Search: Find an element in a sorted array.
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.
Binary Search with Rotated Array: If the array has been rotated, a modified binary search can still find an element.
Binary Search in 2D matrix: Elements are sorted both row-wise and column-wise.
Binary Search to Compute Square Root or Other Mathematical Computations: Binary search can be used to perform some mathematical calculations to a certain precision.
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:
|
|
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)
.