Binary search everywhere?
1 binary search in the practical application of many, but the idea is very simple, is similar to the thought of divide and conquer, for example, if you want to total of $1000 or more to find a specific number, if you turn to look up, of course, but if can look for can determine each want to find the number is not in the other half, is much faster.
Binary lookup is that simple, just remember to find a way to reduce the scope in half, you can use binary lookup.
69 for prescribing
Topic describes
Given a non-negative integer, take the square root of it and round it down.
Example 1
Input: 8 Output: 2 Explanation: The root of 8 is 2.82842… And if I round down, I get 2.
Example 2
Input: 4 Output: 2 Explanation: The square root of 4 is 2.
0 <= x <= 2^ 31-1
Think about 1
And the idea is very simple, because if you’re taking the square root of n, you can look for numbers between 1 and n over 2, so you can use binary search, and if it’s equal to n, you return it, and if it’s greater than n, you look in the smaller half, and if it’s less than n, you look in the larger half
Of course, there are other mathematical solutions to this problem, but we’re just going to look at the idea of binary search, and the other mathematical solutions, you can see for yourself.
To achieve 1
/ * * *@param {number} x
* @return {number}* /
export default (x) => {
const halfX = Math.ceil(x / 2);
let low = 1;
let high = halfX;
while (low <= high) {
let mid = Math.floor(low + (high - low) / 2);
if (mid * mid === x) {
return mid;
} else if (mid * mid < x) {
low = mid + 1;
} else {
high = mid - 1; }}return low * low > x ? low - 1 : low + 1;
};
Copy the codeTime complexity O(LGN /2), space complexity O(1)
34 Search Interval
Topic describes
Given an array of incremented integers and a value, find the first and last occurrence of that value. If it does not exist, both return values are set to -1
The advanced solution is O (LGN) time complexity.
Example 1
Input: nums = [5,7,7,8,8,10], target = 8 output: [3,4] explanation: the number 8 appears for the first time in digit 3 and for the last time in digit 4.
Example 2
Input: nums = [5,7,7,8,8,10] target = 6 output: [-1,-1
Example 3
Input: nums = [3,3,3], target = 3 Output: [0,2
Description 10 <= nums.length <= 10^ 52-10 ^9 <= nums[I] <= 10^9 3-10 ^9 <= target <= 10^9
Think about 1
The idea is simple because the array is in ascending order and indicates O (LGN), which is obviously binary search.
This is also relatively simple, is commonly used binary search, if not found, return [-1,-1] can be
The important thing here is that you want to find the first occurrence of target in the array and the last occurrence of target.
To achieve 1
/ * * *@param {number[]} nums
* @param {number} target
* @return {number[]}* /
export default (nums, target) => {
if (nums.length === 0 || (nums.length === 1 && nums[0] !== target)) {
return [-1, -1];
}
if (nums.length === 1 && nums[0] === target) {
return [0.0];
}
const len = nums.length;
let low = 0;
let high = len - 1;
const res = [];
while (low <= high) {
// To prevent data overflow
let mid = Math.floor(low + (high - low) / 2);
if (nums[mid] === target) {
let minFlag = false;
let maxTemp = mid;
let minTemp = mid;
while (minTemp >= 0 && nums[minTemp] === target) {
minTemp--;
}
if (minTemp + 1! == mid) { res.push(minTemp +1);
} else {
res.push(mid);
}
while (maxTemp < len && nums[maxTemp] === target) {
maxTemp++;
}
if (maxTemp === mid + 1) {
res.push(mid);
} else {
res.push(maxTemp - 1);
}
return res;
}
if (nums[mid] < target) {
low = mid + 1;
}
if (nums[mid] > target) {
high = mid - 1; }}if (res.length === 2) {
return res.sort((a, b) = > a - b);
} else {
return [-1, -1]; }};Copy the codeTime complexity O(LGN), space complexity O(1)
81 Rotate the array to find the number
Topic describes
An originally incremented array is broken end to end (e.g. [1,2,2,3,4,5] → [2,3,4,5,1,2], the first and second bits broken) and is called a rotated array. Given a value, determine whether the value exists in the rotated array. Return true if it exists, false if it does not
Example 1
Input: nums = [2,5,6,0,0,1,2], target = 0 output: true
Example 2
Input: nums = [2,5,6,0,0,1,2], target = 3 output: false
Think about 1
The easiest way to do it is to go straight through the array, but obviously we don’t use that here
You can see that part of the array is in ascending order, and the other part is in ascending order, so the question is how do you find where to split?
Of course it’s possible to go through the array and find two ascending arrays split, but that’s not as good as just going through, not binary searching.
So can we turn it around and say, what if we just use binary search?
Think about it
At first, I wanted to move low and high based on the relationship between mid and mid+1 or mid and mid-1, but it felt very complicated
If nums[mid] is lower than nums[high], then nums[high] is in ascending order. If nums[mid] is in ascending order, then target is in ascending order
If nums[mid] is greater than nums[low], it is also a faction array
If nums[mid] is equal to num[low], we can recalculate mid and target
Nums [mid] = num[high]; nums[mid] = num[high]
But when you run it, you can see that binary lookup takes about the same time as traversing the array.
To achieve 1
/ * * *@param {number[]} nums
* @param {number} target
* @return {boolean}* /
export default (nums, target) => {
if (nums.length === 0| |! nums) {return false;
}
if (nums.length === 1) return nums[0] === target;
let low = 0;
let high = nums.length - 1;
while (low <= high) {
let mid = Math.floor(low + (high - low) / 2);
if (nums[mid] === target) {
return true;
}
if (nums[mid] < nums[high]) {
// Determine if target is in the range
if (target > nums[mid] && target <= nums[high]) {
low = mid + 1;
} else {
high = mid - 1; }}else if (nums[mid] > nums[low]) {
if (target >= nums[low] && target < nums[mid]) {
high = mid - 1;
} else {
low = mid + 1; }}else if (nums[low] === nums[mid]) {
low++;
} else{ high--; }}return false;
};
Copy the codeThe algorithm is O(n), because in the worst case, binary lookup becomes an traversal array. Space complexity O(1)
154 Rotate the array lookup to find the smallest element
Topic describes
Suppose a sorted array performs a “rotation” somewhere to find the smallest element (array elements may be duplicated) that contains repeated numbers
Example 1
Input: [1,3,5] Output: 1
Example 2
Input: [2,2,2,0,1] output: 0
Example 3
Input: [3,3,1,3] output: 1
Example 4
Input: [10,1,10,10] Output: 1
Think about 1
If the target of 81 is the smallest number, you can use the same strategy.
By the way, this question is labeled hard in Leetcode, while 81 is labeled medium, but the difficulty level is about the same, so sometimes it’s not necessary to pay too much attention to the difficulty level
To achieve 1
/ * * *@param {number[]} nums
* @return {number}* /
// 2, 2, 2, 0, 1;
export default (nums) => {
if (nums.length === 0| |! nums) {return false;
}
if (nums.length === 1) return nums[0];
let low = 0;
let high = nums.length - 1;
let min = Number.MAX_VALUE;
while (low <= high) {
let mid = Math.floor(low + (high - low) / 2);
if (nums[mid] < nums[high]) {
high = mid - 1;
min = Math.min(nums[mid], min);
} else if (nums[mid] > nums[low]) {
min = Math.min(nums[low], min);
low = mid + 1;
} else if (nums[low] === nums[mid]) {
min = Math.min(nums[low], min);
low++;
} else {
min = Math.min(nums[high], min); high--; }}return min;
};
Copy the codeThe algorithm is O(n), because in the worst case, binary lookup becomes an traversal array. Space complexity O(1)
540. A single element in an ordered array
Topic describes
Given an ordered array of integers, where every element appears twice and only one number appears only once, find the number.
Example 1
Input: [1,1,2,3,3,4,4,8,8] output: 2
Example 2
Input: [3,3,7,7,10,11,11] output: 10
Note: Your scheme should run in O(log n) time complexity and O(1) space complexity.
Think about 1
It’s very simple, binary search, and the point is because every number in the array except one appears twice, you can tell if the number appears on that side based on whether the subscript of mid is odd or even
If the mid is even, the low to mid has an odd number of figures, so you can judge nums (mids) and nums [mid – 1] are equal, to determine whether the figures appear only once in this side.
It’s a simple idea
To achieve 1
/ * * *@param {number[]} nums
* @return {number}* /
export default (nums) => {
if (nums.length === 1) return nums[0];
let low = 0;
let high = nums.length - 1;
while (low <= high) {
let mid = Math.floor(low + (high - low) / 2);
console.log(low, high, mid);
if (
(mid + 1< nums.length && nums[mid] ! == nums[mid +1] && mid >= 1&& nums[mid] ! == nums[mid -1]) ||
(mid === nums.length - 1&& nums[mid] ! == nums[mid -1]) ||
(mid === 0&& nums[mid] ! == nums[mid +1]) {return nums[mid];
}
if (mid % 2! = =0) {
if (mid >= 1 && nums[mid - 1] === nums[mid]) {
low = mid + 1;
} else {
high = mid - 1; }}else {
if (mid >= 1 && nums[mid] === nums[mid - 1]) {
high = mid - 1;
} else {
low = mid + 1; }}}return nums[low];
};
};
Copy the codeThe algorithm time complexity O(LGN). Space complexity O(1)
4. Find the median of two positive ordinal groups
Topic describes
Given two positively 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.
Advanced: Can you design a time complexity O(log (m+n)) algorithm to solve this problem?
Example 1
Input: nums1 = [1,3], nums2 = [2] output: 2.00000 explanation: merge array = [1,2,3], median 2
Example 2
Input: nums1 = [1,2], nums2 = [3,4] output: 2.50000 description: merge array = [1,2,3,4], median (2 + 3) / 2 = 2.5
Example 3
Input: nums1 = [0,0], nums2 = [0,0] output: 0.00000
Example 4
Input: nums1 = [], nums2 = [1] Output: 1.00000
Example 5
Input: nums1 = [2], nums2 = [] Output: 2.00000
Tip: 1 nums1.length == m 2 nums2.length == n 3 0 <= m <= 1000 4 0 <= n <= 1000 5 1 <= m + n <= 2000 6 -10^6 <= nums1[i], nums2[i] <= 10^6
Think about 1
If you see it for the first time, it’s hard to figure out how to use binary search, but you can think about it, right
Determine the array length of nums1 and nums2. Make nums1 less than or equal to nums2
Suppose k is the median subscript we are looking for after nums1 and nums2 are combined. Here, if nums1 and nums2 are combined with odd length, we can look for the number k = left
const left = Math.floor((nums1Len + nums2Len + 1) / 2)
Copy the codeIf nums1 and nums2 are combined with an even number, we can find the numbers with subscripts at k= left and k=right
const left = Math.floor((nums1Len + nums2Len + 1) / 2);
const right = Math.floor((nums1Len + nums2Len + 2) / 2);
Copy the codeIf nums1[k/2] is greater than nums2[k/2], then the number we are looking for in the k position must be in nums1 and nums2 out of the 0 to k/2 array.
Nums1 [k/2] is greater than nums2[k/2], so we can exclude nums[k/2] before nums[k/2], but we do not know whether nums1[k/2] is greater than nums2[k/2], so we can look for k/2 in the remaining array.
To achieve 1
/ * * *@param {number[]} nums1
* @param {number[]} nums2
* @return {number}* /
const getKth = (nums1, start1, end1, nums2, start2, end2, k) = > {
const len1 = end1 - start1 + 1;
const len2 = end2 - start2 + 1;
// If nums1 is larger than nums2, change the position of the two arrays so that the array length is the smallest in front to prevent
// nums2[start2 + k-1] is in error
if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
if (len1 === 0) return nums2[start2 + k - 1];
if (k === 1) return Math.min(nums1[start1], nums2[start2]);
const i = start1 + Math.min(len1, Math.floor(k / 2)) - 1;
const j = start2 + Math.min(len2, Math.floor(k / 2)) - 1;
const nums1End = Math.min(end1, i + 1);
const nums2End = Math.min(end2, j + 1);
if (nums1[i] > nums2[j]) {
return getKth(nums1, start1, nums1End, nums2, j + 1, end2, k - (j - start2 + 1));
} else {
return getKth(nums1, i + 1, end1, nums2, start2, nums2End, k - (i - start1 + 1)); }};export default (nums1, nums2) => {
if (nums1.length === 0 && nums2.length === 1) {
return nums2[0];
}
if (nums1.length === 1 && nums2.length === 0) {
return nums1[0];
}
const nums1Len = nums1.length;
const nums2Len = nums2.length;
// Find the left and right of the median of odd and even numbers, respectively
const left = Math.floor((nums1Len + nums2Len + 1) / 2);
const right = Math.floor((nums1Len + nums2Len + 2) / 2);
// If it is odd, only search once
if ((nums1Len + nums2Len) % 2! = =0) {
return getKth(nums1, 0, nums1Len - 1, nums2, 0, nums2Len - 1, left);
}
return (
(getKth(nums1, 0, nums1Len - 1, nums2, 0, nums2Len - 1, left) +
getKth(nums1, 0, nums1Len - 1, nums2, 0, nums2Len - 1, right)) *
0.5
);
};
Copy the codeThe algorithm’s time complexity is also easy to understand because m is nums1.length and n is nums2.length because the range of each lookup is reduced by half from (m+n)/2. So the time is order lg(m+n) and the space is order lg(m+n).
Binary search algorithm summary
Binary search is actually a divide-and-conquer idea, if you can narrow down the search scope by half at a time, depending on some conditions, you can almost certainly use binary search.
But some of them may not be obvious, they may need to be transformed, but the idea is that we can keep narrowing down the search, bringing us closer to the answer.