Topic Description (Medium Difficulty)
Finding the first and last occurrence of the target value is also done in log (n).
Let’s start with two solutions provided by Leetcode.
Solution – linear scanning
Traversal from left to right, ending as soon as a value equal to target is present, saving the current subscript. If target is not found from left to right, then return [-1, -1] because target is not found from left to right, then it must not be found from right to left. If found, traverse from right to left, ending as soon as a value equal to target appears, saving the current subscript.
Order n is not enough, but you can see the idea, left to right, right to left we’ve seen it before.
public int[] searchRange(int[] nums, int target) {
int[] targetRange = {-1, -1};
// Scan left to right
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
targetRange[0] = i;
break; }}// If not found before, return [-1, -1]
if (targetRange[0] = = -1) {
return targetRange;
}
// Scan from right to left
for (int j = nums.length-1; j >= 0; j--) {
if (nums[j] == target) {
targetRange[1] = j;
break; }}return targetRange;
}
Copy the codeTime complexity: O (n).
Space complexity: O (1).
The solution is binary search
Let’s look at normal binary search first.
int start = 0;
int end = nums.length - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (target == nums[mid]) {
return mid;
} else if (target < nums[mid]) {
end = mid - 1;
} else {
start = mid + 1; }}Copy the codeIn binary search, we end up with target, and we need to change that.
If we look for the leftmost value equal to target, finding target doesn’t mean we have what we need, as in the following case,
Now mid is equal to target, but what we’re looking for is still on the left, and to get to log time, we’re still throwing away half of it, so we need to update end = mid-1, as shown below.
Tartget > nums [mid] start = mid + 1
Target == nums [mid]; end = mid – 1; start > end; The value we’re looking for is exactly what start points to. So we modify the code as follows:
while (start <= end) {
int mid = (start + end) / 2;
if (target == nums[mid]) {
end = mid - 1;
} else if (target < nums[mid]) {
end = mid -1 ;
} else {
start = mid + 1; }}Copy the codeThe same kind of analytical thinking on the right, which side we need to get rid of.
So the final code comes out. Leetcode is combining the search left and the search right, essentially the same thing.
public int[] searchRange(int[] nums, int target) {
int start = 0;
int end = nums.length - 1;
int[] ans = { -1, -1 };
if (nums.length == 0) {
return ans;
}
while (start <= end) {
int mid = (start + end) / 2;
if (target == nums[mid]) {
end = mid - 1;
} else if (target < nums[mid]) {
end = mid - 1;
} else {
start = mid + 1; }}// Consider whether tartget exists and determine if the value we are looking for is equal to target and out of bounds
if(start == nums.length || nums[ start ] ! = target) {return ans;
} else {
ans[0] = start;
}
ans[0] = start;
start = 0;
end = nums.length - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (target == nums[mid]) {
start = mid + 1;
} else if (target < nums[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
ans[1] = end;
return ans;
}
Copy the codeTime complexity: O (log (n)).
Space complexity: O (1).
Method three
That’s the idea that Leetcode gave me, and I don’t think it’s a very good idea, because it’s always going to loop log n times, so let me show you what I started with.
It is equivalent to optimization on the basis of solution two, and the following is the code for solution two.
while (start <= end) {
int mid = (start + end) / 2;
if (target == nums[mid]) {
end = mid - 1;
} else if (target < nums[mid]) {
end = mid -1 ;
} else {
start = mid + 1; }}Copy the codeSo let’s think about the next case, if we look for the leftmost target, and we’re already looking for mid, and solution two updates to end = mid-1, and then we keep going, and we can stop at this point. If nums[mid-1] is less than nums[mid], then nums[mid] is the correct value.
And, of course, the same idea applies to the far right, so let’s look at the code.
public int[] searchRange(int[] nums, int target) {
int start = 0;
int end = nums.length - 1;
int[] ans = { -1, -1 };
if (nums.length == 0) {
return ans;
}
while (start <= end) {
int mid = (start + end) / 2;
if (target == nums[mid]) {
// This is to deal with the problem of mid-1 crossing the boundary.
// If mid == 0, mid == 0, mid == 0
// Select target > n as the minimum value
// if mid > 0, set nums[mid-1] to n.
int n = mid > 0 ? nums[mid - 1] : Integer.MIN_VALUE;
if (target > n) {
ans[0] = mid;
break;
}
end = mid - 1;
} else if (target < nums[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
start = 0;
end = nums.length - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (target == nums[mid]) {
int n = mid < nums.length - 1 ? nums[mid + 1] : Integer.MAX_VALUE;
if (target < n) {
ans[1] = mid;
break;
}
start = mid + 1;
} else if (target < nums[mid]) {
end = mid - 1;
} else {
start = mid + 1; }}return ans;
}
Copy the codeTime complexity: O (log (n)).
Space complexity: O (1).
@jzw: AC, but if you’re looking for Integer.MIN_VALUE, you’ll get an error. You can modify it.
In addition to being less than n, it also determines whether the current is at both ends.
if (target > n || mid == 0) {
if (target < n || mid == nums.length - 1) {
Copy the codepublic int[] searchRange(int[] nums, int target) {
int start = 0;
int end = nums.length - 1;
int[] ans = { -1, -1 };
if (nums.length == 0) {
return ans;
}
while (start <= end) {
int mid = (start + end) / 2;
if (target == nums[mid]) {
int n = mid > 0 ? nums[mid - 1] : Integer.MIN_VALUE;
if (target > n || mid == 0) {
ans[0] = mid;
break;
}
end = mid - 1;
} else if (target < nums[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
start = 0;
end = nums.length - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (target == nums[mid]) {
int n = mid < nums.length - 1 ? nums[mid + 1] : Integer.MAX_VALUE;
if (target < n || mid == nums.length - 1) {
ans[1] = mid;
break;
}
start = mid + 1;
} else if (target < nums[mid]) {
end = mid - 1;
} else {
start = mid + 1; }}return ans;
}
Copy the codeThe total
In general, this problem is not difficult, the essence is to modify binary search, in order to meet our needs.
See Leetcode.Wang for more details on popular problems.