This article has participated in the activity of "New person creation Ceremony", and started the road of digging gold creation together.
Binary algorithm
Foreword: If given an ordered array, it is required to find the corresponding number in the array. If the number group is traversed by a repeat loop, the time complexity is O(n). If the binary search algorithm is used, some optimization can be made in the time complexity, the time complexity is O(logn).
1. Algorithm idea:
Set two Pointers, one left pointer to the head of the array, and one right pointer to the tail of the array (of course this is based on the meaning of the question, in my example set), and then take the middle value for comparison, and then narrow the search scope.
Note:
The most difficult part of binary algorithm is the processing of boundary cases. If it is not handled well, it will lead to the binary algorithm can not solve the corresponding problems correctly. Here I will introduce several frameworks to you
2. The first one
Find the dichotomy of a number:
int l = 0, r = nums.length - 1;
while(l <= r){
int mid = (l + r) / 2;
if(nums[mid] == target){
return mid;
}else if(nums[mid] < target){
l = mid + 1;
}else if(nums[mid] > target){
r = mid - 1; }}return -1;
Copy the codeTo explain the framework:
1. Whyl <= r?
Because r is the subscript of the last element of the array (r = nums.length-1), we use l <= r. You can modify it if you want, but we recommend not to modify it, because the framework here is consistent with the following, and therefore easy to remember. And the last return value of the following frame has some meaning, so keep this frame in mind with me.
2. Whyl = mid + 1?
If nums[mid] < target and the array is ordered, l = mid + 1, r = mid – 1.
Is 3.int mid = (l + r) / 2The processing of
Int mid = l + (r-l) / 2 int mid = l + (r-L) / 2
So, congratulations on basically mastering the first framework.
3. The second
Right border: directly on code:
int l = 0, r = letters.length - 1;
while(l <= r){
int mid = (l + r) / 2;
if(letters[mid] == target){
l = mid + 1;
}else if(letters[mid] < target){
l = mid + 1;
}else if(letters[mid] > target){
r = mid - 1; }}if(r < 0|| letters[r] ! = target)return -1;
return r;
Copy the codeTo explain the framework:
What was explained in the previous framework is not covered here
1. Why= =When,l = mid + 1?
Because this frame is looking for the index of target, and it’s the index of the rightmost object, so it’s going to go to the right when it’s equal, so it’s going to be l = mid + 1.
2. Why do you add this judgment at the end?
Because at the end of the loop l = r + 1, and l here can be 0, r may be less than 0 at the end, so we need to make a judgment, of course, there is no corresponding target. It also determines whether the value is equal to target.
3. Of course, here’s the returnrThe meaning of
Right boundary method: returns the subscript of the rightmost number if it exists, the subscript of the first number less than the number if it does not exist.
4. The third kind
Left border directly on the code:
public int left_bound(int[] num,int target1){
int l = 0, r = num.length - 1;
while(l <= r){
int mid = l + (r - l) / 2;
if(num[mid] == target1){
r = mid - 1;
}else if(num[mid] < target1){
l = mid + 1;
}else if(num[mid] > target1){
r = mid - 1; }}if(l == num.length || num[l] ! = target)return -1;
return l;
}
Copy the codeTo explain the framework:
1. Why= =When,r = mid - 1?
Because this frame is looking for target, and it’s the index of the leftmost one, so it’s going to be left when it’s equal, so it’s going to be r = mid-1.
2. Why do you add this judgment at the end?
The loop ends with l = r + 1 and r = num. Length – 1, so l may be num. Length – 1. It also determines whether the value is equal to target.
3. Of course, here’s the returnlThe meaning of
Left boundary method: returns the index of the leftmost number if it exists, or less than the number if it does not exist.
5. Corresponding Leetcode title
1. Look for peaks
Peak elements are those whose values are strictly greater than their left and right neighbors. Given an integer array nums, find the peak element and return its index. The array may contain multiple peaks, in which case you simply return the location of any one of the peaks. You can assume that NUMs [-1] = nums[n] = -∞. You have to implement order log n time to solve this problem
Sample:
Input: nums = [1,2,3,1]
Description: 3 is the peak element, and your function should return its index 2.
Input: nums = [1,2,1,3,5,6,4]
Explanation: Your function can return index 1 with a peak element of 2; Or return index 5 with a peak element of 6.
AC code:
This method is referred to as the climbing method, because we need to find any peak, so we can choose which peak depends on the left or right selection corresponding to the first median
class Solution {
public int findPeakElement(int[] nums) {
int l = 0, r = nums.length - 1;
while(l < r){
int mid = (l + r) >> 1;
if(nums[mid] < nums[mid + 1]){
l = mid + 1;
}else{ r = mid; }}returnl; }}Copy the codeUphill stage: Mid + 1 May be the peak value, so L = mid + 1;
if(nums[mid] < nums[mid + 1]){
l = mid + 1;
}
Copy the codeThis is also an uphill phase: mid may also be the peak value, so r = mid;
else{
r = mid;
}
Copy the code2. Sum of two numbers
Given an array of integers in non-decreasing order numbers, find two numbers that add up to the target number. The function should return the subscript values of these two numbers as an array of integers of length 2. The subscript of numbers starts at 1, so the answer array should be 1 <= answer[0] < answer[1] <= numbers. Length. You can assume that each input corresponds to a unique answer, and you can’t reuse the same elements.
Sample:
Type: numbers = [2,7,11,15], target = 9
Output: [1,2] explanation: the sum of 2 and 7 equals the target number 9. So index1 = 1, index2 = 2.
Enter: numbers = [2,3,4], target = 6
Output: [1, 3]
Type: numbers = [-1,0], target = -1
Output: [1, 2]
AC code:
If the sum of two numbers equals a fixed value, you can use binary search, first traversing the first value, then binary search for the second value. The first framework is used. The fastest is the two-pointer algorithm.
for(int i = 0; i < numbers.length; i ++){
int target1 = target - numbers[i];
int l = i + 1, r = numbers.length - 1;
while(l <= r){
int mid = (l + r) >> 1;
if(numbers[mid] == target1){
return new int[]{i + 1,mid + 1};
}else if(numbers[mid] < target1){
l = mid + 1;
}else if(numbers[mid] > target1){
r = mid - 1; }}}return new int[] {-1, -1};
Copy the code3. The smallest subarray
Given an array of n positive integers and a positive integer target. Find the smallest contiguous subarray [numsl, numSL +1,…, numsr-1, numsr] that satisfies the sum and ≥ target, and return its length. If no subarray exists, return 0.
Sample:
Enter: target = 7, nums = [2,3,1,2,4,3]
Description: the subarray [4,3] is the smallest subarray for this condition.
Enter: target = 4, nums = [1,4,4]
Output: 1.
Input: target = 11, nums = [1,1,1,1,1,1,1]
Output: 0
AC code:
Related explanation: the problem of multiple variables, and was to compare again, but by the prefix and the optimization of transformation in order to seek the two corresponding differential prefixes and an array of values to a fixed value, then it can be to determine the value of an array, and then through the add and subtract to find out the value of the corresponding to binary search search the subscript to the corresponding value
class Solution {
public int minSubArrayLen(int target, int[] nums) {
if(nums.length == 0) return 0;
int[] sum = new int[nums.length + 1];
for(int i = 1; i <= nums.length; i ++){
sum[i] = sum[i - 1] + nums[i - 1];
}
int res = Integer.MAX_VALUE;
// In fact, this is an optimization of the violent method. The violent method is to subtract two numbers and the second loop is to find the second number.
// We can first add target and the value of the left endpoint to find the right endpoint, thus optimizing the second loop
// Similar to the topic: Sum of two numbers II (167)
for(int i = 1; i <= nums.length; i ++){
int target1 = target + sum[i - 1];
int bound = left_bound(sum,target1);
if(bound == -1) {break;
}
res = Math.min(res,bound - i + 1);
}
return res == Integer.MAX_VALUE ? 0 : res;
}
// This function is used to find the corresponding number, or the first number greater than the number if it does not exist
public int left_bound(int[] num,int target1){
int l = 0, r = num.length - 1;
while(l <= r){
int mid = l + (r - l) / 2;
if(num[mid] == target1){
r = mid - 1;
}else if(num[mid] < target1){
l = mid + 1;
}else if(num[mid] > target1){
r = mid - 1; }}if(l == num.length) return -1;
returnl; }}Copy the codeSpecial attention:
1. Avoid missing the relevant information
Nums. length + 1 = nums.length + 1 = nums.length + 1 = nums.length + 1
int[] sum = new int[nums.length + 1];
Copy the code2. Use of left boundary method