Binary-Search

介绍二分查找中的三个模板，以 LeetCode 中的习题为例。

首先介绍一下二分查找中使用的术语：

目标 Target —— 你要查找的值索引 Index —— 你要查找的当前位置左、右指示符 Left，Right —— 我们用来维持查找空间的指标中间指示符 Mid —— 我们用来应用条件来确定我们应该向左查找还是向右查找的索引

二分的思想：每次把区间缩小一半，在缩小的过程中一定要保证，答案是在区间里面的，最后答案的区间长度为1的时候，就得到了目标区间。70%的题目都具有某种单调性。（具有单调性，那么是可以使用二分解决；但是使用二分的题目不一定都具有单调性）95% 的题目是存在二段性。

模板1

模板 1 是二分查找的最基础和最基本的形式。这是一个标准的二分查找模板，是非常基础简单的二分查找。模板 1 用于查找可以通过访问数组中的单个索引来确定的元素或条件。模版 1 不需要后处理，因为每一步中，你都在检查是否找到了元素。如果到达末尾，则知道未找到该元素。

语法关键：

初始条件：left = 0, right = length-1 终止：left > right 向左查找：right = mid-1 向右查找：left = mid+1

模版#1 对应的例题为： LeetCode69 x 的平方根 LeetCode374 猜数字大小 LeetCode33 搜索旋转排序数组

69. Sqrt(x)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution:
    # 二分做法， log n 的时间复杂度
    def mySqrt(self, x: int) -> int:
        if x ==1: return x
        l =0
        r  = x-1
        while l < r:
            mid = l  + r +1 >>1 # 这个是处理溢出问题
            if mid * mid <= x: l =mid
            else: r  =mid -1
        return l 

c++ 实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution {
public:
    int mySqrt(int x) {
        if(x ==1) return x;
        long long l =0, r =x -1; // 可以进一步缩小 r 的范围  r = x/2 +1
        while( l <r)
        {
            long long mid = l +r +1ll >>1;
            if( mid * mid <= x) l =mid;
            else r =mid -1;
        }
        return l;
    }
};

模板2

模板 2 是二分查找的高级模板。它用于查找需要访问数组中当前索引及其直接右邻居索引的元素或条件。查找条件需要访问元素的直接右邻居。使用元素的右邻居来确定是否满足条件，并决定是向左还是向右。保证查找空间在每一步中至少有 2 个元素。需要进行后处理。当你剩下 1 个元素时，循环 / 递归结束。需要评估剩余元素是否符合条件。

语法关键：

初始条件：left = 0, right = length 终止：left == right 向左查找：right = mid 向右查找：left = mid+1

模版#2 对应的例题为： LeetCode278 第一个错误的版本 LeetCode75 寻找峰值 LeetCode159 寻找旋转排序数组中的最小值

LeetCode69 x 的平方根

LeetCode69 x 的平方根

实现 int sqrt(int x) 函数。

需要处理一下 int 类型数字越界的问题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution {
public:
    typedef long long ll;
    int mySqrt(int x) {
        ll l =0, r =x;
        while(l <r)
        {
            ll mid = l +1ll+r >>1;
            
            if(mid *mid <= x) l =mid;
            else r =mid -1;
        }
        return l;   
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
public:
    // 使用二分进行求解, 时间复杂度是logn
    // 二分有两种更新方式， 一种是 l =mid, r =mid -1; 一种是 l =mid +1, r =mid 这个记住也是不难的，r 只能是mid 或者是 mid -1； l 只能是mid 或者是mid +1
    // 并且这种mid +-1 操作只能出现一次。当出现mid -1 那么就需要设置一下 mid = (l +r +1ll )/2 ，防止陷入死循环。通过观察可以知道，都是需要出席 +1 这种操作
    int mySqrt(int x) {
        int l =0, r =x;
        while(l < r)
        {
            int mid =(l +r +1ll) /2;
            if(mid <= x/mid) l =mid;
            else r =mid -1;
        }
        return l;
    }
};

python解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        l, r =0, x
        while l < r:
            mid = l+r +1 >>1
            if(mid *mid <= x):
                l =mid
            else: r =mid -1
        return l

374. Guess Number Higher or Lower

这个题目有bug 吧，说反了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


// Forward declaration of guess API.
// @param num, your guess
// @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num);
class Solution {
public:
    int guessNumber(int n) {
        int l =1, r =n;
        
        while(l <r)
        {
            int mid = (l+r) /2;
            if(guess(mid) ==0) return mid;
            else if(guess(mid) == 1) l =mid +1;
            else r = mid -1;
        }
        return l;
    }
};

c++ 中使用二分解法，很容易出现int 溢出的这种现象。所以注意一下使用long long进行解决

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


// Forward declaration of guess API.
// @param num, your guess
// @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num);
class Solution {
public:
    // 凡是能够分块处理的，那么都是可以使用二分的进行处理的
    // 一部分满足某种条件，一部分满足另一种条件
    typedef long long ll;
    int guessNumber(int n) {
        ll l =1, r =n;
        while(l <r)
        {
            ll mid =l +r >>1;
            if(guess(mid) == 0) return mid;
            else if (guess(mid) ==-1) r =mid -1;
            else l =mid +1;
            //cout << l <<" "<< r<< endl;
        }
        return l;
    }
};

python 解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


# The guess API is already defined for you.
# @param num, your guess
# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
# def guess(num):

class Solution(object):
    def guessNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        l, r = 1, n
        while l<r:
            mid = l+r >>1
            if( guess(mid) ==0): return mid
            elif (guess(mid) ==1): 
                l =mid +1
            else: 
                r =mid -1
        return l
            
 

Search in Rotated Sorted Array

这个题目非常的经典的，使用了一个二分，时间复杂度是 $logn$，解释可以参考这里

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


class Solution {
public:
    //数据特点， 分成了左右两个递增序列， nums[0] > 后面的递增序列的
    int search(vector<int>& nums, int target) {
        int n =nums.size();
        if (n ==0) return -1;
        int l=0, r =nums.size() -1;
        while(l <r)
        {
            int mid = (l+r) >>1;
            
            if(nums[mid] >= nums[0])
            {
                if( target >= nums[0] && target <= nums[mid])
                    r =mid ;
                else
                    l =mid +1;   
            }
            else
            {
                if(target <nums[0] && target >nums[mid])
                    l =mid +1;
                else
                    r =mid;
            }
        }
        return target == nums[l] ? l : -1;
    }
};

这个是属于 python实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums:
            return -1
        l,r =0, len(nums) -1
        while l <r:
            mid = l +r >>1
            if nums[mid] >= nums[0]:
                
                if target >= nums[0] and target <= nums[mid]:
                    r =mid 
                else:
                    l =mid +1
            else:
                if target > nums[mid] and target <= nums[0]:
                    l =mid +1
                else:
                    r =mid
        if l< len(nums) and nums[l] == target:
            return l
        return -1

so easy

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.size() ==0) return -1;
        int n =nums.size() ;
        int l =0, r =n -1;
        while(l <r)
        {
            int mid = l +r >>1;
            
            if(nums[mid] >= nums[0])
            {
                if(target >= nums[0] && target <= nums[mid])
                    r =mid;
                else
                    l =mid +1;
            }
            else
            {
                if(target < nums[0] && target > nums[mid])
                    l =mid +1;
                else
                    r =mid;
            }
        }
        if(l <n && nums[l] ==target) return l;
        return -1;   
    }
};

Search in Rotated Sorted Array II

这种做法是比较好的， LeetCode平台上两个 90%，可以近似的看成 $logn$

深刻理解 if ... else ... 是分类的思想。假设真值位于 if 中，假设位于 else

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


class Solution {
public:
    // 这个是33 有点类似，只是多了可能存在重复的数字，所以要保证二分的条件，保证的是严格的单调性
    bool search(vector<int>& nums, int target) {
        
        int n =nums.size();
        if(n ==0) return false;
        if(target == nums[0]) return true;
        int k =n -1;
        while(k >=0 && nums[k] ==nums[0]) k --;
        n =k;
        // 然后现在就是不
        int l =0, r =n;
        
        while(l <r)
        {
            int mid = (l+r) >>1;
            
            if(nums[mid] >= nums[0])
            {
                if( target >= nums[0] && target <= nums[mid])
                    r =mid ;
                else
                    l =mid +1;   
            }
            else
            {
                if(target <nums[0] && target >nums[mid])
                    l =mid +1;
                else
                    r =mid;
            }
        }
        return nums[l] ==target? true:false;
    }
};

这个和上一道题目是类似的。在进行 – 操作的时候，一定要判断一下是否能够–，比如代码中的 i>=0 然后才能进行 –；如果 i<n ，那么才能进行 ++操作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class Solution {
public:
    // 这个和上面的题目的区别，可能有重复的元素， 所以需要先处理一下。保证前一部分的元素是绝对大于后面的元素的
    bool search(vector<int>& nums, int target) {
        if(nums.size() ==0) return false;
        int n =nums.size();
        int l =0, r =n -1;
        while(r >=0 && nums[0] ==nums[r]) r --; 
        // 那么现在之前的方式就可以使用了
        while(l <r)
        {
            int mid = l +r >>1;

            if(nums[mid] >= nums[0])
            {
                if(target >= nums[0] && target <= nums[mid])
                    r =mid;
                else
                    l =mid +1;
            }
            else
            {
                if(target < nums[0] && target > nums[mid])
                    l =mid +1;
                else
                    r =mid;
            }
        }
        if(l <n && nums[l] ==target) return true;
        return false;   
    }
};

python 求解。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


class Solution:
    """
    二分要保证严格的单调性
    if ... else ... 是分类讨论
    """
    def search(self, nums: List[int], target: int) -> bool:

        n =len(nums)
        if not nums: return -1
        
        l, r =0, len(nums) -1
        while l <r and nums[r] == nums[0]:
            r -=1
        
        while l <r:
            mid =l +r >>1
            if nums[mid] >= nums[0]:
                if target >= nums[0] and target <= nums[mid] :
                    r =mid
                else:
                    l =mid +1
            else:
                if target > nums[mid] and target < nums[0]:
                    l =mid +1
                else:
                    r =mid

        return nums[l] == target

Find Peak Element

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
public:
    // 这个关键是要 会使用二分进行求解
    int findPeakElement(vector<int>& nums) {
        int n =nums.size() ;
        if(n ==0) return -1;
        int l =0, r =n -1;
        while(l <r)
        {
            int mid = l +r+1 >>1;
            if(nums[mid] > nums[mid -1]) l =mid;
            else r =mid -1; 
        }
        return l;
    }
};

如果说知道这个考点是二分，那么还是很简单的，在判断条件时候，需要注意下.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int n =nums.size();
        int l  =0, r =n-1;
        while(l <r)
        {
            int mid =l +r >>1;
            
            if(mid +1 <n && nums[mid] <= nums[mid +1]) l =mid +1;
            else r  =mid;
        }
        return l;
    }
};

Find First and Last Position of Element in Sorted Array

划分结点的选择，一定是假定mid 就是那个能够划分成两个部分的结点。好好理解一下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


class Solution {
public:
    // 自己写这种函数的的时候，一定要以 mid 作为分裂点看
    vector<int> searchRange(vector<int>& nums, int target) {
        
        int n =nums.size();
        if (n ==0) return vector<int>{-1, -1};
        
        int l =0, r =n-1;
        while(l <r)
        {
            int mid = l +r >>1;
            
            if(nums[mid] < target) l =mid+1 ;
            else r =mid ;
        }
        //cout << l << endl;
        if(nums[l] != target) return vector<int>{-1, -1};
        
        int left =l;
        l =0, r =n-1;
        while(l <r)
        {
            int mid =l +r +1>>1;
            if(nums[mid]> target ) r =mid -1;
            else l =mid ;
        }
        int right =l;
        
        if(left>=0 && l< n) return vector<int>{left, right};
        return vector<int>{-1, -1};
        
    }
};

需要注意一些细节，其他的都还好.注意可以直接使用 vector res{-1,-1} 这样的形式进行初始化

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class Solution {
public:
    // 有重复的元素，找到重复元素的首尾，使用两次 二分
    // 起点的左边是严格小于 element, 右边是大于等于;
    // 终点的右边是严格大于 element，左边是小于等于
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res{-1, -1};
        if(nums.size() ==0) return res;
        int n =nums.size();
        int l =0, r =n -1;
        while(l <r)
        {
            int mid = l+r >>1;
            if(nums[mid] < target) l =mid +1;
            else r =mid;
        }
        if(l >= n || nums[l] != target) return res;
        int left = l;
        
        l =0, r =n -1;
        while(l <r)
        {
            int mid = l+r+1 >>1;
            if(nums[mid] > target) r =mid-1;
            else l =mid;
        }
        if(l >=n) return res;
        return vector<int>{left, l};

        
    }
};

LeetCode278 第一个错误的版本

由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

题目非常简单，直接套用模板#2即可。此题与模板#1的最大区别就在于，right不能修改为mid-1，而必须修改为mid。因为当如果mid是错误产品，无法判断第一个错误版本在mid之前，还是就是当前mid。这是模板#2与模板#1的最大不同。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution {
public:
    int firstBadVersion(int n) {
        long left = 0;
        long right = n;
        while(left<right){
            long mid = (left+right)/2; //计算中点
            if(isBadVersion(mid)==false) left = mid+1; //如果mid是正常产品，证明第一个错误产品在右侧
            if(isBadVersion(mid)==true) right = mid; //如果mid是错误产品，证明第一个错误产品在是自己或者在左侧
        }
        return left;
    }
};

153. Find Minimum in Rotated Sorted Array

使用二分的思想，关键找到分割点。关键是思路：发现最小元素前面的元素都是大于等于 arr[0]，最小元素后面的元素都是小于 arr[0]，所以这个就是分割点。该题目假设一定存在最小值，并且数字之间是没有重复元素的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
public:
    int findMin(vector<int>& nums) {
        if( !nums.size() ) return -1;
        if(nums.back() > nums[0])  return nums[0];
        int l =0, r = nums.size() -1;
        while (l <r){
            
            int mid = l +r >> 1;
            
            if(nums[mid] >= nums[0]) l = mid +1;
            else r =mid;
        }
        return nums[l];
    }
};

python 实现。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution(object):
    def findMin(self, nums):
        if not nums: return nums;
        if nums[-1] > nums[0]: return nums[0]
        l =0
        r =len(nums) -1
        while l <r:
            mid = l +r >>1;
            if nums[mid] >= nums[0]:
                l =mid +1
            else:
                r =mid
        return nums[l]

Find Minimum in Rotated Sorted Array II

如果有重复的元素，那么是从右边开始进行比较。好好考虑这种合理性。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
public:
    // 对于这种 duplicates 是很容出来的
    int findMin(vector<int>& arr) {
        int n =arr.size();
        if(n ==1) return arr[0];
        if(arr[0] < arr.back()) return arr[0];
        int l =0, r =n -1;
        while(l <r)
        {
            int mid = l +r >>1;
            if(arr[mid] > arr[r]) l =mid +1;
            else if(arr[mid] < arr[r]) r =mid;
            else r --;
        }
        return arr[l];
    }
};

解题的思路，先是处理主题的内容，使用二分的做法，然后处理一个case 的东西，比如重复的元素或者是正序的情况。注意 r >0 而不是 r>=0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution {
public:
    // 在旋转数组中寻找最小的值
    int findMin(vector<int>& nums) {
        int n =nums.size();
        if(n ==1) return nums[0];
        int l=0, r =n -1;
        // 处理重复的, r > 0 这个很重要呀，不是 >=0
        while(r >0 &&nums[r] ==nums[l]) r --;
        // 处理正序的情况
        if(nums[l] < nums[r]) return nums[l];
        while(l <r)
        {
            int mid =l +r >>1;
            
            if(nums[mid] >= nums[0]) l =mid +1;
            else r =mid;
        }
        return nums[l];
    }
};

对于二分的解法，时间复杂度是 $O(logn)$，因为每次都是可以去掉一部分数字。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
    // 如果第 i 个版本是错误的，那么 i+1 也一定是错误的，所以 i 构成了二分的条件
    int firstBadVersion(int n) {
        int l =1, r =n;
        while(l <r)
        {
            int mid = l +0ll +r >>1;
            
            if(isBadVersion(mid)) r =mid ;
            else l =mid +1;
        }
        return l;
    }
};

isBadVersion

时间复杂度是$O(logn)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


// Forward declaration of isBadVersion API.
bool isBadVersion(int version);
class Solution {
public:
    // 二分的本质是可以分块查找，找到一个分界点，左边是一种情况，右边是另一种情况。
    //mid 是坏的版本，r =mid， 如果mid 是好的版本， l =mid +1 （这种加一 or 之间等于是根据实际问题作出的选择）
    // 然后根据这种情况，去选择第一个或者是第二个版本的模板
    int firstBadVersion(int n) {
        int l =1, r =n;
        while(l <r)
        {
            int mid = (0ll+l +r )/2; // 这个可能产生溢出的问题， 注意细节，如果 0ll 放到了最后，那么同样是会溢出，因为三个数相加本质上是两个数先相加然后加上第三个数
            if(isBadVersion(mid))  r =mid;
            else l =mid +1;
        }
        return l;
    }
};

Find Minimum in Rotated Sorted Array

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


class Solution {
public:
    // 最小值前面的数字都满足 nums[i] >= nums[0]， 最小值后面的数字都不满足
    // 这个就形成了分块（可以使用二分）
    // 如果 nums[mid] >= nums[0] , l =mid +1,  r =mid
    int findMin(vector<int>& nums) {
        
        // 注意这个是严格的大于号，因为没有重复元素，所以可以这么操作
        if(nums.back() > nums[0]) return nums[0];
        
        // 这个是边界问题的一种处理方法， 这个是一种方式（关键是不影响时间复杂度的，常数级别的）
        /*
        if(nums.size() <=5)
        {
            int min_v =INT_MAX;
            for(auto u : nums)
                min_v =min(min_v, u);
            return min_v;
        }
        */
        int l =0, r =nums.size() -1;
        while(l <r)
        {
            int mid =(l +r )/2;
            if( nums[mid] >=nums[0]) l =mid +1;
            else r =mid;
        }
        return nums[l];
    }
};

模板3

模板 3 是二分查找的另一种独特形式。它用于搜索需要访问当前索引及其在数组中的直接左右邻居索引的元素或条件。搜索条件需要访问元素的直接左右邻居。使用元素的邻居来确定它是向右还是向左。保证查找空间在每个步骤中至少有 3 个元素。需要进行后处理。当剩下 2 个元素时，循环 / 递归结束。需要评估其余元素是否符合条件。

对应的leetcode 例题 LeetCode34 在排序数组中查找元素的第一个和最后一个位置 LeetCode658 找到 K 个最接近的元素

语法关键：

初始条件：left = 0, right = length-1 终止：left + 1 == right 向左查找：right = mid 向右查找：left = mid

binarySearch 模板题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


int binarySearch(vector<int>& nums, int target){
    if (nums.size() == 0)
        return -1;

    int left = 0, right = nums.size() - 1;
    while (left + 1 < right){
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid;
        } else {
            right = mid;
        }
    }
    // Post-processing:
    // End Condition: left + 1 == right
    if(nums[left] == target) return left;
    if(nums[right] == target) return right;
    return -1;
}

来个模板, 所谓的访问文件保留几个元素，就是包括与否mid 的意思。如果 left 和 right 都可以为 mid，那么就是三个访问空间；如果只有 left or right 可以= mid，那么就是两个访问空间；如果 left =mid -1 且 right =mid +1 那么只有一个访问空间。同样三个条件依次为 left <= right, left < right 和 left +1 < right 保证访问空间是可以 access 的。

总结如下：

Find K Closest Elements

这个算法太精妙了，真的是难以理解了。总的时间复杂度 $O(log(n -k) +k)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution {
public:
    //时间复杂度 O(log (n-k) +k)
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int n = arr.size();
        int l =0, r =n -k;
        while( l< r)
        {
            int mid = l +r >>1;
            if(x -arr[mid]  > arr[mid+k]  -x) l =mid +1;
            else r =mid;
        }
        return vector<int>(arr.begin() +l, arr.begin() +l+k);
    }
};

关键是是二分的条件比较难想，可以使用极端的思路，如果 x - arr[mid] 之间的距离是大于 arr[mid+k] -x 那么这个是需要调整 l 的距离，然后靠近 mid` ;反之，也是成立的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
public:
    // 使用二分的思想， 时间复杂度是logn 的
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int n =arr.size() ;
        int l =0, r = n -k;
        while(l <r)
        {
            int mid =l +r >>1;
            if(x - arr[mid] > arr[mid+k] -x) l =mid +1;
            else r =mid;
        }
        // 这种写法也是需要多加学习的
        return vector<int>{arr.begin() +l, arr.begin() +l +k};
    }
};

浮点数二分算法

浮点二分不存在 +1 还是 -1 的操作，需要注意的是精度问题。

数的三次方根

double 和 float 的区别： float ：单精度浮点数在机内占4个字节，用32位二进制描述。 double：双精度浮点数在机内占8个字节，用64位二进制描述。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


#include<iostream>
using namespace std;
double x;
int main()
{
    cin >>x;
    double l = -10000, r = 100000;
    // 如果是保留6 位消失，那么使用 1e-8，如果是2位，那么是 1e-4
    while(r -l > 1e-8)
    {
        double mid = (l+r) /2;
        if(mid *mid *mid >x) r =mid;
        else l =mid;
    }
    printf("%.6f", l);// 输出的格式 %.6f 表示double 类型
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


#include<bits/stdc++.h>
using namespace std;
int main()
{
    double n;
    cin >>n;
    double l =-10000, r = 10000;
    while(r -l > 1e-8)
    {
        double mid = (l+r) /2;
        
        if(mid *mid *mid > n) r =mid;
        else l =mid;
    }
    printf("%.6f\n", l);
    return 0;
}

参考文献：

数据结构也不难：二分查找模版与例题

python 对于 binary search 的支持

包函数 bisect

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


import bisect
 
L = [1,3,3,6,8,12,15]
x = 3
 
x_insert_point = bisect.bisect_left(L,x)　　#在L中查找x，x存在时返回x左侧的位置，x不存在返回应该插入的位置..这是3存在于列表中，返回左侧位置１
print x_insert_point
 
x_insert_point = bisect.bisect_right(L,x)  #在L中查找x，x存在时返回x右侧的位置，x不存在返回应该插入的位置..这是3存在于列表中，返回右侧位置３
 
print x_insert_point
 
x_insort_left = bisect.insort_left(L,x)  #将x插入到列表L中，x存在时插入在左侧
print L
 
x_insort_rigth = bisect.insort_right(L,x) #将x插入到列表L中，x存在时插入在右侧　　　　
 

防止越界的tips： change “mid = (low + high) / 2 " -> “mid = low + (high - low) / 2 “或者使用 ”mid = (low + high) » 1“，

文章目录

模板1

模板2

模板3

python 对于 binary search 的支持