Binary search

basis

Basic writing (elements without duplication)

int binarySearch(vector<int> &A, int target) {
    // [left, right]
    int left = 0, right = (int)A.size() - 1;
    while (left <= right) {
        int mid = left + (right - left)/2;
        if (A[mid] == target) {
            return mid;
        } else if(A[mid] > target) {
            right = mid - 1;
        } else if (A[mid] < target) {
            left = mid + 1; }}return - 1;
}

// Write recursively
int binarySearchRecur(vector<int> &A, int target, int left, int right) {
    if (left > right) { return - 1; }
    int mid = left + (right - left)/2;
    if (A[mid] > target) {
        return binarySearchRecur(A, target, left, mid- 1);
    } else if (A[mid] < target) {
        return binarySearchRecur(A, target, mid + 1, right);
    } else {
        returnmid; }}Copy the code

Find the left boundary

Look for the location where the element first appeared.

    int searchLeftBound(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(target == nums[mid]) {
                right = mid - 1;
            } else if(target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1; }}if(left < nums.size() && nums[left] == target) {
            return left;
        } 
        return - 1;
    }
Copy the code

Look for the left margin less than the target element

int binarySearchLeftBound(vector<int> &A, int target) {
    // [left, right]
    int left = 0, right = (int)A.size() - 1;
    while (left <= right) {
        int mid = left + (right - left)/2;
        if (A[mid] == target) {
            right = mid - 1;
        } else if (A[mid] > target) {
            right = mid - 1;
        } else if (A[mid] < target) {
            left = mid + 1; }}return left - 1;
}
Copy the code

Find the right boundary

Look for the last time the element was seen

int searchRightBound(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(target == nums[mid]) {
            left = mid + 1;
        } else if(target < nums[mid]) {
            right = mid - 1;
        } else {
            left = mid + 1; }}if(right >= 0 && nums[right] == target) {
        return right;
    }
    return - 1;
}
Copy the code

Look for the right edge, larger than the target element

int binarySearchRightBound(vector<int> &A, int target) {
    // [left, right]
    int left = 0, right = (int)A.size() - 1;
    while (left <= right) {
        int mid = left + (right - left)/2;
        if (A[mid] == target) {
            //[mid, right]
            left = mid + 1;
        } else if (A[mid] > target) {
            right = mid - 1;
        } else if (A[mid] < target) {
            left = mid + 1; }}return left;
}
Copy the code

LeetCode topic

Easy topic

704. Binary search

374. Guess the size of the number

278. The first incorrect version

Medium topic

34. Find the first and last position of the element in the sorted array (find the left and right bounds of the target value)

The most immediate idea is to look for the left boundary first and then the right boundary:

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = searchLeftBound(nums, target);
        int right = searchRightBound(nums, target);
        vector<int> v;
        v.push_back(left); v.push_back(right);
        return v;
    }

    int searchLeftBound(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(target == nums[mid]) {
                right = mid - 1;
            } else if(target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1; }}if(left < nums.size() && nums[left] == target) {
            return left;
        } 
        return - 1;
    }
    int searchRightBound(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(target == nums[mid]) {
                left = mid + 1;
            } else if(target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1; }}if(right >= 0 && nums[right] == target) {
            return right;
        }
        return - 1; }};Copy the code

658. Find K elements closest to each other.

Rotation problem

33. Search for a rotating sort array (no duplicate elements, find the target value)

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] >= nums[left]) {
                // In... left... mid... [left, mid] ascending
                if(target == nums[mid]) {
                    return mid;
                } else if(target >= nums[left] && target < nums[mid]) {
                    / /... left... target... mid...
                    right = mid - 1;
                } else {
                    // Target may be left... mid... target? .
                    left = mid + 1; }}else {
                [mid, right] is in ascending order
                if(target == nums[mid]) {
                    return mid;
                } else if(target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1; }}}return - 1; }};Copy the code

The idea is to determine which range the target is in, and the rest is easy to do. Just follow the binary search template.

Nums [mid] >= nums[left] = nums[left] = nums[left]

81. Search for rotation sort array II(duplicate elements, find target value)

class Solution {
public:
    bool 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] > nums[left]) {
                if(target == nums[mid]) {
                    return true;
                } else if(target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1; }}else if(nums[mid] == nums[left]) {
                if(target == nums[left]) {
                    return true;
                } else {
                    left = left + 1; }}else {
                if(target == nums[mid]) {
                    return true;
                } else if(target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1; }}}return false; }};Copy the code

And no repetition of the same idea, but to deal with repeated elements, so singled out to deal with, because do not know the specific situation, so only one to.

153. Find the minimum value in a rotating sort array (no duplicate elements, find the minimum value)

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] >= nums[left]) {
                if(nums[left] > nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1; }}else {
                if(nums[left] > nums[right]) {
                    left = left + 1;
                } else {
                    right = mid - 1; }}}returnnums[left]; }};Copy the code

This is the same way you would write a rotating array, where you decide how much to go up and how much to go down, and then you keep shrinking the space

Another way to write it is to think about the right-hand side, because the right-hand side is more likely to be small, and there are fewer conditions to think about

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while(left < right) {// left == mid == right
            int mid = left + (right - left) / 2;
            if(nums[mid] < nums[right]) {
                right = mid;
            } else {
                left = mid + 1; }}returnnums[left]; }};Copy the code

Find the minimum value II in the rotation sort array (if there is a duplicate value, find the minimum value)

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while(left < right) {// left == mid == right
            int mid = left + (right - left) / 2;
            if(nums[mid] < nums[right]) {
                right = mid;
            } else if(nums[mid] == nums[right]) {
                right = right - 1;
            } else {
                left = mid + 1; }}returnnums[left]; }};Copy the code

Nums [mid] == nums[right] == nums[right]

// Mid is sitting at the table
[2.2.2.2.2.2.2.2.2.0.2.2]
// Mid is on the right
[2.2.0.2.2.2.2.2.2.2.2.2]
// Since we are not sure about these two cases, we will treat them separately and gradually approach the minimum value
Copy the code

Peak problem

The problem is the continuation of the rotation array

162. Look for peaks

binary

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 1, right = arr.size() - 1;// [1, n - 1]
        while(left < right) {
            int mid = left + (right - left + 1) / 2;
            if(arr[mid - 1] < arr[mid]) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
};
Copy the code

Usually, we use “dichotomy” to search the value, and we need to ensure that the sequence itself meets the “dichotomy” : after selecting an endpoint (the reference value), we combine the “one paragraph meets and the other paragraph does not meet” to achieve the “half” search effect.

But we’re trying to figure out the top index, so if we select either the top or the bottom of the array, we can’t actually “directly” split the array into two segments based on size.

However, we can find the following properties by using the question: Since arR values are different, the left side of the peak element must satisfy strict monotone increase, while the right side of the peak element must not.

Therefore, the arR array with the peak element as the split point is binary according to the size relationship with the previous element/the last element:

• The left side of the summit element satisfies the property ARR [i-1] < ARR [I] ARR [I −1]< ARR [I], while the right side does not
• The right side of the summit element satisfies the property ARR [I]> ARR [I +1] ARR [I]> ARR [I +1], while the left side does not

Note: When calculating mid, you must round up, otherwise you will loop indefinitely

Three points

In fact, we can also use “three points” to solve the problem.

As the name suggests, “tripling” is dividing an interval into three with two endpoints, and then approximating the target by rejecting a third of the interval at a time.

Specifically, since the peak element is the global maximum, we can divide the current interval into three sections each time: [L, m1], **[m1,m2] ** and **[m2, r]**. If arr[m1] > ARr [m2], it means that the peak element cannot exist in [m2, r]. Let r = m2-1. Same thing with the other interval.

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 0, right = arr.size() - 1;// [1, n - 1]
        while(left < right) {
            int m1 = left + (right - left) / 3;
            int m2 = right - (right - left) / 3;
            if(arr[m1] > arr[m2]) {
                right = m2 - 1;
            } else {
                left = m1 + 1; }}returnleft; }};Copy the code

Index to the summit of the array of mountains

reference

Brush question route