Dichotomy template
Template 1
The exit condition for template 1 is I <= j, which means I > j below the end of the loop.
public static int search(int[] arr, int target) {
int i = 0, j = arr.length - 1;
while (i <= j) { // The exit condition is I > j
int m = i + ((j - i) >> 1);
if (arr[m] == target) {
return m;
}
if (arr[m] > target) {
j = m - 1;
} else {
i = m + 1; }}// now, i == j + 1
return -1;
}
Copy the codeThe square root of x
Title: Compute and return the square root of x, which is a non-negative integer, leaving only the decimal part.
There is no negative 1 return in this problem.
- Using the template above, the right endpoint j starts at x/2+1;
- Without return m, the loop terminates with I > j, and since only fractional parts are kept, j is eventually returned, which is close to and slightly less than the square root of x.
class Solution {
public int mySqrt(int x) {
int i = 0, j = x / 2 + 1;
while (i <= j) {
int m = i + ((j - i) >> 1);
if ((long) m * m == x) {
return m;
}
if ((long) m * m > x) {
j = m - 1;
} else {
i = m + 1; }}returnj; }}Copy the codeSearch the rotation sort array (leetcode 33)
Search for the specified number in an ascending rotation array with no duplicate numbers, return -1 if not found.
If the middle number is not target, we need to search in which interval according to the size relationship between the middle number and the edge number.
- The middle number is compared to the left endpoint
class Solution {
public int search(int[] nums, int target) {
int i = 0, j = nums.length - 1;
while (i <= j) {
int m = i + ((j - i) >> 1);
if (nums[m] == target) {
return m;
}
if (nums[m] == nums[i]) { // The middle number is equal to the left endpoint, i.e. I == m == j-1
i++;
} else if (nums[m] > nums[i]) { // The left half is ordered
if (target >= nums[i] && target < nums[m]) { // In the left half
j = m - 1;
} else { // In the right half
i = m + 1; }}else if (nums[m] < nums[i]) { // The right half of the interval is ordered
if (target > nums[m] && target < nums[i]) { // In the right half
i = m + 1;
} else { // In the left half
j = m - 1; }}}return -1; }}Copy the code- The middle number is compared to the right endpoint
class Solution {
public int search(int[] nums, int target) {
int i = 0, j = nums.length - 1;
while (i <= j) {
int m = i + ((j - i) >> 1);
if (nums[m] == target) {
return m;
}
if (nums[m] == nums[j]) { Return (I == j == m);
j--;
} else if (nums[m] > nums[j]) { // The left half is ordered
if (target >= nums[i] && target < nums[m]) { // In the left half
j = m - 1;
} else { // In the right half
i = m + 1; }}else { // nums[m] < nums[j] right half interval order
if (target > nums[m] && target <= nums[j]) { // In the right half
i = m + 1;
} else { // In the left half
j = m - 1; }}}return -1; }}Copy the codeThe template 2
When using this template, sometimes there is no target, but instead the intermediate value is compared to the adjacent value or the left and right endpoint values.
public static int search(int[] arr, int target) {
int i = 0, j = arr.length - 1;
while (i < j) {
int m = i + ((j - i) >> 1);
if (arr[m] == target) {
return m;
}
if (arr[m] < target) {
i = m + 1;
} else {
j = m; // Keep the element slightly larger than target}}// do something
}
Copy the codeFind the minimum value in the rotation sort array (leetcode 153)
Find the minimum value in a rotated array with different elements.
Idea: Use the median value and the right endpoint to compare, gradually narrow the search scope.
The array can be rotated 0 times or more than 0 times, for example: [1, 2, 3, 4, 5] – rotating zero [5, 1, 2, 3, 4] – rotating one [4, 5, 1, 2, 3] – spinning twice [3, 4, 5, 1, 2] – rotating three [2, 3, 4, 5, Nums [m] < nums[j] the minimum value is in the left interval (j = m) when the median value is compared with the left endpoint because there are 0 rotations. Nums [m] > NUMs [j] minimum values in the right interval (I = m + 1).
- Compared to the right endpoint
class Solution {
public int findMin(int[] nums) {
int i = 0, j = nums.length - 1;
while (i < j) {
int m = i + ((j - i) >> 1);
if (nums[m] == nums[j]) { // i == j == m
return nums[m];
}
if (nums[m] > nums[j]) { // The minimum value is on the right
i = m + 1;
} else { // nums[m] < nums[j]j = m; }}returnnums[i]; }}Copy the code- Compared to the left endpoint
To compare it to the left endpoint, you have to exclude 0 rotations. An array that was rotated multiple times at the beginning may be rotated zero times over the course of the loop. Nums [I] and NUMs [j].
class Solution {
public int findMin(int[] nums) {
int i = 0, j = nums.length - 1;
while (i < j) {
int m = i + (j - i) / 2;
// Exclude rotation 0 times
if (nums[i] < nums[j]) {
return nums[i];
}
if (nums[m] == nums[i]) { // m == i == j - 1
return nums[j]; Nums [I] > nums[j] = nums[j];
}
if (nums[m] < nums[i]) {
j = m;
} else { // nums[m] > nums[i]
i = m + 1; }}returnnums[i]; }}Copy the codeTemplate 3
The main difference between the three templates is the while condition, and the range of elements that can be used within a while loop block. For template 3, you can use elements at positions I, I +1, and I +2 in the loop.
When I exit the loop, I +1==j, leaving the elements at positions I and j.
public static int search(int[] arr, int target) {
int i = 0, j = arr.length - 1;
while (i + 1 < j) {
int m = i + ((j - i) >> 1);
if (arr[m] == target) {
return m;
}
if (arr[m] < target) {
i = m;
} else {
j = m; // Keep the element slightly larger than target}}// do something
}
Copy the codeRotation array problem summary
33 Search rotation sort array template 1 has been solved.
Unlike array 33, elements in array 81 can be repeated. Returns true/false.
Searching a rotated array is similar to 81, but returns the one equal and with the smallest index.
153 Finding the minimum value in the rotation sort array has been solved in template 2.
Unlike 153, the elements in the array can be repeated.
Search rotated sorted array II
The code is exactly the same as the code without repeating elements, except that the return value is changed to true/false.
Now I’m going to use the middle value to compare to the right endpoint
class Solution {
public boolean search(int[] nums, int target) {
int i = 0, j = nums.length - 1;
while (i <= j) {
int m = i + ((j - i) >> 1);
if (nums[m] == target) {
return true;
}
if (nums[m] == nums[j]) {
j--;
} else if (nums[m] > nums[j]) {
if (target >= nums[i] && target < nums[m]) {
j = m - 1;
} else {
i = m + 1; }}else { // nums[m] < nums[j]
if (target > nums[m] & target <= nums[j]) {
i = m + 1;
} else {
j = m - 1; }}}return false; }}Copy the codeSearch rotation array
The code for this problem is similar to the previous problem, but instead of returning directly if the median value is equal to target, the left range is searched for a smaller index. This also results in the condition that the loop cannot terminate with I <= j, because the loop cannot terminate when arr[j] is equal to target and j== I +1.
In addition, if the same values appear on both sides of the array, the first time the interval is determined, the index may be searched for the larger interval, so judge this situation at the end of the loop.
There is no such thing as the same value on both sides of a subinterval, so the logic inside the loop is the same as in the previous two searches for a rotated array.
class Solution {
public int search(int[] arr, int target) {
int i = 0, j = arr.length - 1;
while (i < j) {
int m = i + ((j - i) >> 1);
if (arr[m] == target) {
j = m;
} else {
if (arr[m] == arr[j]) {
j--;
} else if (arr[m] > arr[j]) {
if (target >= arr[i] && target < arr[m]) {
j = m - 1;
} else {
i = m + 1; }}else { // arr[m] < arr[j]
if (target > arr[m] && target <= arr[j]) {
i = m + 1;
} else {
j = m - 1; }}}}if (arr[i] == target) {
if (arr[0] == arr[i]) {
return 0;
} else {
returni; }}return -1; }}Copy the codeFind the minimum value II in the rotation sort array
Similar to the code logic of I. When the middle number is equal to the right endpoint, the interval cannot be determined, and there is nums[m] already in the interval, so we can remove the nums[j] on the edge without eliminating the minimum value, and can also narrow the range.
class Solution {
public int findMin(int[] nums) {
int i = 0, j = nums.length - 1;
while (i < j) {
int m = i + ((j - i) >> 1);
if (nums[m] == nums[j]) {
j--;
} else if (nums[m] > nums[j]) {
i = m + 1;
} else { // nums[m] < nums[j]j = m; }}returnnums[i]; }}Copy the codeconclusion
The topics for searching rotated arrays fall into two categories:
- Searches for the specified value in the rotation array
- Search for the minimum value in the rotation array
In addition, whether an element is repeated or not is slightly changed in the way it is written without affecting the code framework.
You can uniformly compare the intermediate value with the right endpoint.
Classification discussion, the points are greater than or equal to, than merging greater than or equal to or less than or equal to the idea of clearer.