I. Introduction
Dichotomy, also known as bisection search, half-fold search, is a search algorithm to find a particular element in an ordered array. The core idea is that by comparing the target data with the ordered data sequence, each search splits the data sequence in half, determining which half of the target data is in, until the target data is found or the target data is determined to not exist. The time complexity of bisection is O(log n), which is more efficient compared to the O(n) of sequential lookup. However, in practice, we may encounter some special cases that require certain variants of the bisection method to meet specific needs. In this article, we will introduce several common variants of bisection, and give a Java implementation.
II. Dichotomy variants
- Finds the first element equal to the given value
In some cases, we need to not only determine whether an element exists in an array, but also find the first position of that element in the array. This can be accomplished with a slight modification of binary lookup. Instead of returning immediately when the target element is found, we continue to look to the left until we find the first element equal to the target value.
The Java implementation is as follows:
public int findFirstEqual(int[] nums, int target) {
int left = 0, right = - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
right = mid - 1; // Continue searching to the left
} else {
left = mid + 1;
}
}
// Check if left is out of bounds and if nums[left] is equal to target.
if (left >= 0 && nums[left] == target) {
return left;
} else {
return -1; // Not found
}
}
- Finds the last element equal to the given value
Similar to finding the first element equal to a given value, we can find the last element equal to a given value by modifying the binary lookup algorithm. When the target element is found, we do not return immediately, but continue to look to the right until we find the last element equal to the target value.
The Java implementation is as follows:
public int findLastEqual(int[] nums, int target) {
int left = 0, right = - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1; // Keep looking to the right
}
}
// Check if right is out of bounds and nums[right] is equal to target.
if (right >= 0 && nums[right] == target) {
return right;
} else {
return -1; // Not found
}
}
- Find insertion location
In some cases, we need to insert an element into an ordered array and return the index of the inserted element. If the element already exists in the array, the index of the element is returned; otherwise, the position where it should be inserted is returned. Again, this can be accomplished by modifying the binary lookup algorithm.
The Java implementation is as follows:
public int searchInsert(int[] nums, int target) {
int left = 0, right = - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid; // Find the target element and return its index
} else if (nums[mid] < target) {
left = mid + 1; // The target element is in the right half
} else {
right = mid - 1; // the target element is in the left half or doesn't exist (in which case target should be inserted at the position pointed to by right)
}
}
// Returns the position where the target element should be inserted if it is not found.
return left;
}
III. Summary
This article describes three common variants of bisection: finding the first element equal to a given value, finding the last element equal to a given value, and finding the insertion position, and gives the corresponding Java implementations. These variants are based on the original bisection lookup algorithm with some modifications and extensions to meet specific needs. In practical applications, we can choose the appropriate variant algorithm to solve the problem according to the specific problem.
to this article on the Java implementation of dichotomous variant of the sample code of the article is introduced to this, more related to Java dichotomous variant of the content, please search for my previous articles or continue to browse the following related articles I hope that you will have more support for me in the future!