This is the second day of my participation in the August More Text Challenge

This article is a sequel to a previous article that challenged day one’s introduction to dichotomy. Most of the time, the actual situation we encounter is more than just finding the corresponding number. When there may be the same number in the array, there may be multiple target values in the array, and the actual situation may require us to find the left or right edge of the target value range. We will continue to assume that arrays are sorted from smallest to largest.

The logarithmic time complexity of dichotomy cannot be guaranteed by using linear traversal to the left or right after finding a target value. Instead of returning a target value when it is found, you should narrow your search further.

Find the left boundary

When the target value is found, instead of returning immediately, you should further narrow the right boundary

Here is an example of a closed left open right case:

if(target==nums[mid])
{
right=mid;
}
Copy the code

Since the target value is not returned directly, it must be returned at the end of the while loop, where left==right

The return value

When left==right-1, where there is only one element between left and right, mid must be less than right. Assuming we can find the target value in the array, in the closed and open case, right should be the index of the last target value on the right, and left is moving closer to right, so we can return either left or right.

But we also have to consider the case where there is no target value in the array.

Since left=0 and right=length, mid must be less than right. In extreme cases (left is always equal to mid+1, or right is always equal to mid, refer to the previous formula), the final left boundary is [0,length].

if(nums[mid]<target)
    {
        left=mid+1;
    }
else if(nums[mid]>target)
    {
        right=mid;
    }
Copy the code

For a left bound index, index==0 can either mean that the first left number is its left bound, or it can mean that no corresponding number is found at all.

But if index==length, there is only one case where the corresponding number is not found. In other words, the value of the left margin is really “how many values in the array are smaller than me”.

An example of code to determine the return value is given below.

If (left==nums.length) {return -1; } else if(left==0) { if(target==nums[left]) {return left; } else {return -1; } } else { return left; }Copy the code

You can simplify it even further by merging the same logic

if(left==nums.length) { return -1; } return target==nums[left]? left:-1;Copy the code

Find the right boundary

Similarly, when we find the target value, we can not immediately return, but increase the left margin to continue searching.

if(target==nums[mid])
{
left=mid+1;
}
Copy the code
The return value

Finding the return value of the right boundary is important, assuming we can find the target value in the array. In the case of left closed and right open, left is generally equal to the subscript +1 of the last target value on the left, so we can return left-1 or right-1.

Judge the boundary case the other way around

if(left==0) { return -1; } return target==nums[left-1]? left-1:-1;Copy the code