BinarySearch - 二叉搜索

算法

二叉中重要的地方在于退出循环的条件以及判断边界时的等号是否需要

Template标准板

int search(vector<int> & nums, int target)
{
    if(nums.size() == 0) return -1;
    int lo = 0, hi = nums.size() - 1;
    while(lo <= hi)
    {
        int mid = lo + (hi - lo) / 2;
        if(nums[mid] == target) return mid;
        else if(target < nums[mid]) hi = mid - 1;
        else lo = mid + 1;
    }
    return -1;
}

找出下标，不存在则返回-1

数组已排好序
- 可认为数组中没有重复元素

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.size() < 1) return -1;
        return binarySearch(nums, 0, nums.size() - 1, target);
    }
    int binarySearch(vector<int>& nums, int lo, int hi, int target)
    {
        if(lo >= hi && nums[lo] == target) return lo;
        if(lo >= hi && nums[lo] != target) return -1;
        //prevent lo + hi overflow
        int mid = lo + (hi - lo) / 2;
        if(target <= nums[mid]){
            return binarySearch(nums, lo, mid, target);
        }else{
            return binarySearch(nums, mid + 1, hi, target);
        }
    }
};

求开方

int mySqrt(int x) {
        long long r = x;
        while(r * r > x)
            r = (r + x / r) / 2;
        return r;
    }

0 - x（或x/2）是有序的，所以可以利用折半查找的方法

class Solution {
public:
    int mySqrt(int x) {
        if(x == 0) return 0;
        int lo = 1, hi = x, ans = 0;
        while (lo <= hi)
        {
            int mid = lo + (hi - lo) / 2;
            if (x / mid < mid) //防止溢出
            {
                hi = mid - 1;
            }
            else
            {
                lo = mid + 1;
                ans = mid;
            }
        }
        return ans;
    }
};

旋转排序的数组搜索

旋转排序，即并非从左到右排序，如[4, 5, 6, 7, 1, 2, 3]
该算法思路是将数组转化为[4, 5, 6, 7, INF, INF, INF]或[-INF, -INF, -INF, -INF, 1, 2, 3] (INF表示正无穷)进行折半搜索，

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int lo = 0, hi = nums.size();
        while (lo < hi) {
        int mid = (lo + hi) / 2;
        double num = (nums[mid] < nums[0]) == (target < nums[0])
                   ? nums[mid]
                   : target < nums[0] ? -INFINITY : INFINITY;
        if (num < target)
            lo = mid + 1;
        else if (num > target)
            hi = mid;
        else
            return mid;
        }
        return -1;
    }
};

Find First Peek 找到第一个峰

https://leetcode.com/explore/learn/card/binary-search/126/template-ii/948/

if(nums.size() == 0) return -1;
if(nums.size() == 1) return 0;
if(nums.size() == 2)
{
    if(nums[0] < nums[1]) return 1;
    else return 0;
}
int lo = 0, hi = nums.size() - 1;
while(lo < hi)
{
    int mid = lo + (hi - lo) / 2;
    if(nums[mid - 1] < nums[mid] && 
       nums[mid] < nums[mid + 1])
    {
        lo = mid + 1;
    }else
    {
        hi = mid;
    }
}
return lo;

找到循环有序的序列的最小数

int findMin(vector<int>& nums) {
    if(nums.size() == 0) return -1;
    if(nums.size() == 1) return nums[0];
    int lo = 0, hi = nums.size() - 1;
    while(lo + 1 < hi)
    {
        if(nums[lo] < nums[hi]) return nums[lo];
        int mid = lo + (hi - lo) / 2;
        if(nums[0] < nums[mid])
        {
            lo = mid;
        }else{
            hi = mid;
        }
    }
    if(nums[hi] >= nums[0]) return nums[lo]; // hi 肯定 != 0，不要用lo与0元素比较，否则无法区分[1, 2]和[2, 1] 
    else return nums[hi];
}

Search for a Range 搜索范围

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,

Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

正常二分查找设置中点使用的是mid = lo + (hi - lo) / 2，这样会使搜索范围向左移，最终会使得lo = mid而不会使hi = mid，因此容易搜索到target范围的前置哨兵（端点），这里使用一个技巧，使用mid = lo + (hi - lo) / 2 + 1设置中点，可以得到target范围的后置哨兵。
算法两次折半查找，时间复杂度是$O(logN)$，空间复杂度是$O(1)$

vector<int> searchRange(vector<int>& nums, int target) {
    vector<int> ret(2, -1);
    if(nums.size() == 0) return ret;
    int lo = 0, hi = nums.size() - 1;
    while(lo < hi)
    {
        int mid = lo + (hi - lo) / 2;
        if(target > nums[mid])
        {
            lo = mid + 1;
        }else{
            hi = mid;
        }
    }
    if(nums[lo] != target) return ret;
    else ret[0] = lo;
    hi = nums.size() - 1;
    while(lo < hi)
    {
        int mid = lo + (hi - lo) / 2 + 1; // important
        if(target < nums[mid])
        {
            hi = mid - 1;
        }else{
            lo = mid;
        }
    }
    ret[1] = hi;
    return ret;
}

Find K Closest Elements

Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

Example 1:

Input: [1,2,3,4,5], k=4, x=3
Output: [1,2,3,4]

Example 2:

Input: [1,2,3,4,5], k=4, x=-1
Output: [1,2,3,4]

Note:

• The value k is positive and will always be smaller than the length of the sorted array.
• Length of the given array is positive and will not exceed 104
• Absolute value of elements in the array and x will not exceed 104

先找到x或者比x稍大的元素的位置，然后整理出k个元素，返回。

时间复杂度: 搜索$O(logN)$ + 整理k个元素$O(k)$ = $O(logN + k)$
空间复杂度: $O(1)$

vector<int> findClosestElements(vector<int>& arr, int k, int x) {
    if(x < arr[0]) return vector<int>(arr.begin(), arr.begin()+k);
    if(x > arr[arr.size() - 1]) return vector<int>(arr.end() - k, arr.end());
    int lo = 0, hi = arr.size() - 1;
    while(lo < hi)
    {
        int mid = lo + (hi - lo) / 2;
        if(arr[mid] == x) { hi = mid; break;}
        if(arr[mid] < x) lo = mid + 1;
        else hi = mid - 1;    
    }
    // hi指向x或者 >= x 的第一个元素
    lo = hi;
    hi ++;
    // 找出k个元素
    while(k)
    {
        if(hi >= arr.size() || lo >= 0 && x - arr[lo] <= arr[hi] - x)
        {
            lo --;
        }else
        {
            hi ++;
        }
        k--;
    }
    //                                 ↓这里要加1
    return vector<int>(arr.begin() + lo + 1, arr.begin() + hi);
}