It is well known that dichotomy is very efficient in finding specific elements in ordered arrays in order time O(logN).
In general, binary lookup is used nine times out of ten for search problems requiring O(logN) time complexity.
Note: Take care to avoid overflow when finding the midpoint of the dichotomy method. The addition of two 32-bit positive integers may cause overflow.
The following sort out the common routine of dichotomy:
Routine 1: Search for the position in an array equal to an element
This kind of problem is basically a set of dichotomy template, dichotomy template arrangement is as follows:
public int binarySearch(int[] nums, int target) {
int left = 0, right = nums.length - 1;
int mid;
while (left <= right) {
mid = ((right - left) >> 1) + left; // Left + right / 2 is not used to prevent overflow
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1; }}return -1; / / not found
}
Copy the codeExamples of this type of question are as follows:
LeetCode 74: Search a two-dimensional matrix
Write an efficient algorithm to determine whether there is a target value in an M x N matrix. The matrix has the following properties: the integers in each row are arranged in ascending order from left to right. The first integer in each line is greater than the last integer in the previous line.
Analytic: by the questions, you can see that each line on the number of the first is greater than the number of the last the line, if the two dimensional array as a one-dimensional array, so the whole array is strictly ascending, can be directly to use template, the only problem is to change the one dimensional array index, into a two dimensional array index, the transformation, it is very simple: Assuming that the index of the one-dimensional array is I and the size of the two-dimensional array is m x n, the position of I in the two-dimensional array is: I/n, I % n.
The answer:
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int left = 0, right = m * n - 1;
int mid;
while (left <= right) {
mid = ((right - left) >> 1) + left;
if (matrix[mid/n][mid%n] == target) {
return true;
}
if (matrix[mid/n][mid%n] < target) {
left = mid + 1;
} else {
right = mid - 1; }}return false;
}
Copy the codeRoutine 2: Search for the smallest position in an array greater than or equal to an element
This is also a common pattern, which returns the index of an element if it exists, and the index of an element that should be inserted into an array if it does not exist.
public int binarySearchInsert(int[] nums, int target) {
int left = 0, right = nums.length - 1, ans = nums.length;
int mid;
while (left <= right) {
mid = ((right - left) >> 1) + left; // Left + right / 2 is not used to prevent overflow
if (nums[mid] >= target) { // When the midpoint value is greater than or equal to the value you are looking for, record the location and search on the left
ans = mid;
right = mid - 1;
} else {
left = mid + 1; }}return ans;
}
Copy the codeExamples of this type of questions are as follows:
Find the first and last positions of elements in a sorted array
Given an ascending array of integers, nums, and a target value, target. Find the starting and ending positions of the given target value in the array. If no target value exists in the array, return [-1, -1].
The starting position is the first position greater than or equal to the element, and the ending position is the position greater than or equal to the element.
The answer:
private int binarySearch(int[] nums, int target, boolean lower) {
int left = 0, right = nums.length - 1, ans = nums.length;
while (left <= right) {
int mid = ((right - left) >> 1) + left;
// There are different conditions depending on whether elements are included or not
if (nums[mid] > target || (lower && nums[mid] == target)) {
right = mid - 1;
ans = mid;
} else {
left = mid + 1; }}return ans;
}
public int[] searchRange(int[] nums, int target) {
int leftIndex = binarySearch(nums, target, true);
int rightIndex = binarySearch(nums, target, false) - 1;
if (leftIndex < nums.length && nums[leftIndex] == target && rightIndex < nums.length){
return new int[]{leftIndex, rightIndex};
}
return new int[] {-1, -1};
}
Copy the codeRoutine 3: Search for an element in a partially ordered array
The essence of dichotomy is to quickly reduce the search scope in an ordered array. However, most of the time, the condition given is not to search in a completely ordered array. At this time, it is necessary to make full use of the ordered part to reduce the search range, and flexibly use the above two templates to write high-performance code quickly.
LeetCode 33 题 : Search rotated sorted arrays
The integer array nums is arranged in ascending order. The values in the array are different.
Before passing to the function, nums is rotated on some previously unknown subscript k (0 <= k < nums.length), Make the array [nums [k], nums [k + 1),…, nums] [n – 1, nums [0], nums [1],…, nums [k – 1]] (subscript starting from 0). ,1,2,4,5,6,7 [0], for example, in the subscript 3 after rotation may become,5,6,7,0,1,2 [4].
Give you the rotated array nums and an integer target, return its subscript if nums contains the target value, otherwise -1.
The size of the rotated array is zigzag, ascending from subscript 0 to one position, and then ascending from the next position to the end. The number of elements in the first segment is larger than the number in the second segment.
Suppose we search by dichotomy, take the middle element, if the middle element falls in the first segment, then the segment from the starting point to the middle element is ordered; If the middle element falls in the second paragraph, the middle element is ordered to the end paragraph.
That is to say, no matter what, there is always a section of elements is ordered, so the ordered elements of this section can determine which part of the target element.
The answer:
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = ((right - left) >> 1) + left;
if (nums[mid] == target) {
return mid;
}
if(nums[left] <= nums[mid])if(target >= nums[left] && target < nums[mid]) {/ / If target is in the upper part of the element, the search range is in the upper part of the element1;
} else {
left = mid + 1; }}else{/ / The second half is in orderif(target <= nums[right] && target > nums[mid]){/ / If target is in the middle of the element, the search range is left = mid +1;
} else {
right = mid- 1; }}}return -1;
}
Copy the codeLeetCode 81 题 : Search the rotated sorted array II
Given that there is an array of integers in non-descending order, nums, the values in the array need not be different from each other.
Before passing to the function, nums is rotated on some previously unknown subscript k (0 <= k < nums.length), Make the array [nums [k], nums [k + 1),…, nums] [n – 1, nums [0], nums [1],…, nums [k – 1]] (subscript starting from 0). ,1,2,4,4,4,5,6,6,7 [0], for example, in the subscript 5 after rotation may become,5,6,6,7,0,1,2,4,4 [4].
Given a rotated array of nums and an integer target, write a function to determine whether the given target value exists in the array. Return true if the target value exists in nums, false otherwise.
The main difference is that the elements in the array can be duplicated. And we’re going to do the same thing, but there’s a special point here: because we have the same elements, we could rotate around and say that the leftmost element is equal to the middle element is equal to the rightmost element, and then we can’t tell which one is in order. So you can only move the left and right edges one place to the middle.
The answer:
public boolean search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = ((right - left) >> 1) + left;
if (nums[mid] == target) {
return true;
}
if (nums[mid] == nums[left] && nums[mid] == nums[right]) {
left++;
right--;
continue;
}
if (nums[left] <= nums[mid]) {
if (target < nums[mid] && target >= nums[left]) {
right = mid - 1;
} else {
left = mid + 1; }}else {
if (target <= nums[right] && target > nums[mid]) {
left = mid + 1;
} else {
right = mid - 1; }}}return false;
}
Copy the codeLeetCode 4 题 : Find two positive ordinal group medians
Title: Given two positive ordered (from small to large) arrays of size m and n, nums1 and nums2. Please find and return the median of the two positive ordinal groups.
For two arrays with an odd number of elements (2 * k + 1), we are looking for the k + 1 element. For an array with an even number of elements (2 * k), we are looking for the k + 1 element. So the problem becomes how to find the KTH element in two ordered arrays. The idea here is to find the k / 2 element in the first array, the k / 2 element in the second array, the k / 2 element can’t be in the smaller k / 2 element. That cuts the search area in half. In addition, we need to pay attention to a lot of boundary problems, so we can’t subscript out of bounds.
The answer:
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n = nums1.length + nums2.length;
if (n % 2= =1) {
return findKth(nums1, nums2, n / 2 + 1) * 1.0;
} else {
return (findKth(nums1, nums2, n / 2) + findKth(nums1, nums2, n / 2 + 1)) / 2.0; }}private int findKth(int[] nums1, int[] nums2, int k) {
int index1 = 0, index2 = 0;
int newIndex1, newIndex2;
while (true) {
if (index1 == nums1.length) {
return nums2[index2 + k - 1];
}
if (index2 == nums2.length) {
return nums1[index1 + k - 1];
}
if (k == 1) {
return Math.min(nums1[index1], nums2[index2]);
}
newIndex1 = Math.min(index1 + k / 2, nums1.length) - 1; NewIndex2 = math.min (index2 + k /2, nums2.length) - 1;
if (nums1[newIndex1] < nums2[newIndex2]) {
k -= (newIndex1 - index1 + 1);
index1 = newIndex1 + 1;
} else {
k -= (newIndex2 - index2 + 1);
index2 = newIndex2 + 1; }}}Copy the codeClick here to further communicate with me