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 = 4Output:4Explanation: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.