Binary Search, also known as Binary Search, is an efficient search method. However, the half search requires that the linear table must be used Sequential storage structure And the elements in the table are arranged in order by keywords.
General binary search template
int binarySearch(vector<int>& nums, int target){
if(nums.size() == 0)
return -1;
int left = 0, right = nums.size() - 1;
while(left <= right){
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if(nums[mid] == target){ return mid; }
else if(nums[mid] < target) { left = mid + 1; }
else { right = mid - 1; }
}
// End Condition: left > right
return -1;
}Initial condition: left = 0, right = length-1
Termination: left > right
Find left: right = mid-1
Find right: left = mid+1
When the loop ends, the element is not found
Force buckle 278 First wrong version Buckle: square root of x
If x {is not a negative integer, it returns an arithmetic root.
Since the return type is an integer, only the integer part will be retained and the decimal part will be rounded off.
Note: it is not allowed to use any built-in exponential functions and operators, such as pow(x, 0.5) or x ** 0.5.
Example 1:
Input: x = 4
Output: 2
Example 2:
Input: x = 8
Output: 2
Explanation: the arithmetic square root of 8 is 2.82842, Since the return type is an integer, the decimal part will be rounded off.
Link: https://leetcode-cn.com/leetbook/read/binary-search/xe9cog/
Source: LeetCode
class Solution {
public:
int mySqrt(int x) {
if(x<2){return x;}
int low=0,high=x;
while(low<=high)
{
int mid=(low)+(high-low)/2;
//Anti overflow equal to (low+high)/2
if(mid==x/mid)
{
//mid*mid will overflow here
return mid;
}else if(mid<x/mid)
{
//mid*mid is less than the value to find
//Go to the big range
low=mid+1;
}else{
//If mid*mid is greater than x, look between cells
high=mid-1;
}
}
return high;
}
};Binary search template II
Template 2 is an advanced template for binary search. It is used to find the elements or conditions that need to access the current index and its direct right neighbor index in the array.
int binarySearch(vector<int>& nums, int target){
if(nums.size() == 0)
return -1;
int left = 0, right = nums.size();
while(left < right){
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if(nums[mid] == target){ return mid; }
else if(nums[mid] < target) { left = mid + 1; }
else { right = mid; }
}
// Post-processing:
// End Condition: left == right
if(left != nums.size() && nums[left] == target) return left;
return -1;
}Key attributes
An advanced method of binary search.
The lookup condition requires the direct right neighbor of the access element.
The right neighbor of the element is used to determine whether the condition is met and whether it is left or right.
Ensure that the search space has at least 2 elements in each step.
Post treatment is required. When you have 1 element left, the loop / recursion ends. The remaining elements need to be evaluated for eligibility.
Distinguishing grammar
Initial condition: left = 0, right = length
Termination: left == right
Find left: right = mid
Find right: left = mid+1
Link: https://leetcode-cn.com/leetbook/read/binary-search/xerqxt/
Source: LeetCode
Force buckle 278 First wrong version
You are a product manager and are currently leading a team to develop new products. Unfortunately, the latest version of your product has not passed the quality test. Since each version is developed based on the previous version, all versions after the wrong version are wrong.
Suppose you have n versions [1, 2,..., n], you want to find the first wrong version that causes errors in all subsequent versions.
You can call the bool isBadVersion(version) interface to determine whether the version number is wrong in the unit test. Implement a function to find the first wrong version. You should minimize the number of calls to the API.
Example 1:
Input:n = 5, bad = 4 Output:4 Explanation: call isBadVersion(3) -> false call isBadVersion(5) -> true call isBadVersion(4) -> true Therefore, 4 is the first wrong version.
Example 2: Input: n = 1, bad = 1 Output: 1 Source: LeetCode Link: https://leetcode-cn.com/leetbook/read/binary-search/xe5fpe/
code
class Solution {
public:
int firstBadVersion(int n) {
if(n==1){return 1;}
int left=1,right=n;//The left critical point is 1
//Start with the first version
while(left<right)
{
int mid=(left)+(right-left)/2;
if (isBadVersion(mid)) {
right = mid;
// The answer is in the interval [left, mid]
} else {
left = mid + 1;
// The answer is in the interval [mid+1, right]
}
}
// At this time, there is left == right, and the interval is reduced to one point, which is the answer
return left;
}
};Search rotation sort array
The integer array nums is arranged in ascending order, and the values in the array are different from each other.
Before passing to the function, Num rotates on a previously unknown subscript k (0 < = k < num.length), making the array [num [k], Num [K + 1], nums[n-1], nums[0], nums[1], ..., Nums [k-1]] (subscript counts from 0). For example, [0,1,2,4,5,6,7] may become [4,5,6,7,0,1,2] after being rotated at subscript 3.
Give you the rotated array num and an integer target. If the target value target exists in num, return its subscript, otherwise return - 1.
Example 1:
Input: num = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: num = [4,5,6,7,0,1,2], target = 3
Output: - 1
Example 3:
Input: num = [1], target = 0
Output: - 1
Advanced: can you design a solution with time complexity of O(log n)?
class Solution {
public:
int search(vector<int>& nums, int target) {
int left=0,right=nums.size()-1;
while(left<=right)
{
int mid=left+(right-left)/2;
if(nums[mid]==target)
{
return mid;
}
if(nums[mid]>nums[right]){
if(nums[mid]>target&&target>=nums[left]){
right=mid-1;
}
else{
left=mid+1;
}
}
else{
if(nums[mid]<target&&target<=nums[right]){
left=mid+1;
}
else{
right=mid-1;
}
}
}
return -1;
}
};This question is not well understood
Find peak
The peak element refers to the element whose value is strictly greater than the left and right adjacent values.
Give you an integer array {nums, find the peak element and return its index. The array may contain multiple peaks. In this case, just return the location of any peak.
You can assume that ∞ num [- 1] = num [n] = - ∞.
You must implement an algorithm with a time complexity of O(log n) to solve this problem.
Example 1:
Input: num = [1,2,3,1]
Output: 2
Explanation: 3 is the peak element, and your function should return its index 2.
Example 2:
Input: num = [1,2,1,3,5,6,4]
Output: 1 or 5
Explanation: your function can return index 1, and its peak element is 2; Or return index 5, whose peak element is 6
Link: https://leetcode-cn.com/leetbook/read/binary-search/xem7js/
Source: LeetCode
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int left=0,right=nums.size()-1;
while(left<right)
{
int mid=left+(right-left)/2;
if(nums[mid]<nums[mid+1])
{
left=mid+1;
}else{
right=mid;
}
}
return left;
}
};Summary: the main idea is to halve ， compare the search value with the median value each time ， and the time complexity is O(log n)
If the median value is smaller than the search value, it indicates that the search value is on the right, that is, the interval [mid+1,right]
If the median value is larger than the search value, the search value is on the left, i.e. the interval [left,mid-1]
Because mid equals the search value, that is to find {all the intervals to pay attention to
The end condition is to find the search value or {left > right (no search value)
The advanced application of binary search is a little difficult to understand. I still have to brush more questions and see more.