有序的序列，每次都是以序列的中间位置的数来与待查找的关键字进行比较，每次缩小一半的查找范围，直到匹配成功。
一个情景：将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

图片说明：

优缺点：

优点是比较次数少，查找速度快，平均性能好；

其缺点是要求待查表为有序表，且插入删除困难。

因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

使用条件：

查找序列是顺序结构，有序。

代码：

注意这里在评论区指出来使用int middle=(left+right)/2 ; 存在整数溢出的风险，应改为 int middle=left+(right-left)/2 ; 因为int是4字节，有一定范围。如果两个其中一个很大，相加容易超出这个范围，改成相减的形式可以一定程度避免。这种写法值得推崇！

递归法(不太好)：


//两种实现方式，第一种使用递归法
    public static int search(int[] nums, int key, int left, int right){
        if(nums[left]>key||nums[right]<key||left>right) {
            return -1;
        }
        int middle=left+(right-left)/2
        //说明要查找的在数组左边
        if(key<nums[middle]){
            return search(nums,key,left,middle-1);
        }
        else if(key>nums[middle]){
            return search(nums,key,middle+1,right);
        }
        else {
            return middle;
        }
    }

非递归法：


 //第二种使用非递归法
    public static int fei(int []nums,int key) {
        int left = 0;
        int right = nums.length - 1;
        int middle=left+(right-left)/2;
        while (left <= right) {
            middle=(left + right) / 2;
            if(key==nums[middle]) return middle;
            if (key < nums[middle]) {
                right = middle - 1;
            } 
            else 
              {
                left = middle + 1;
              }
       
        return -1;
    }

时间复杂度

采用的是分治策略

最坏的情况下两种方式时间复杂度一样：O(log2 N)

最好情况下为O（1）

空间复杂度：

算法的空间复杂度并不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数
非递归方式：
由于辅助空间是常数级别的所以：
空间复杂度是O(1);
递归方式：

递归的次数和深度都是log2 N,每次所需要的辅助空间都是常数级别的：
空间复杂度：O(log2N )

整数二分模板：

地址：

LeetCode暑期刷题打卡2019——Week1 二分专题_哔哩哔哩_bilibili

核心思想是想办法将绿色的左边界或者是红色的右边界包含在内

二分模板一共有两个，分别适用于不同情况。

算法思路：假设目标值在闭区间[l, r]中，每次将区间长度缩小一半，当l = r时，我们就找到了目标值。

版本一：

当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。

模板：


int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;//防止int溢出，这里的>>相当于位运算是向右移动一位，相当于是/2
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

版本二：

特别注意：为了防止死循环计算mid时需要加1。

当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid;，

模板：


int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}


class Solution {
   public int[] searchRange(int[] nums, int target) {
	    int []goal= {-1,-1};
		if(nums.length==0)   return goal;
	    //先找元素的第一个位置
	    int l=0,r=nums.length-1;
	    while(l<r){
	        int middle=l+r>>1;
	        if(nums[middle]>=target) r=middle;
	        else l=middle+1;
	    }
	    //由于我们找的是>=target的数，所以当找到的数！=target，说明数组里面没有target这个数
	    if(nums[r]!=target) return goal;
	     int first=r;
	    //然后找元素的最后一个位置
	    int left=0,right=nums.length-1;
	    while(left<right){
	        int middle=left+right+1>>1;
	        if(nums[middle]<=target) left=middle;
	        else right=middle-1;
	    }
	    //这里不需要判断<=target的最后一个数是不是=target了，因为如果前面没有target这个数直接返回{-1,-1}
	    int last=right;
	    goal[0]=first;
	    goal[1]=last;
	    return goal;
	    }
}

浮点数二分模板：


bool check(double x) {/* ... */} // 检查x是否满足某种性质
 
double bsearch_3(double l, double r)
{   //一般来说如果要保留4位小数eps就取1e-6，保留6位小数就取1e-8
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        //这里不用考虑边界了
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

例题：

浮点数：Acwing790（数的三次方根）--------（二分法）

描述:

代码：

注意这里的n，l，r都要申明为double

确定范围时，这里的r！=n

因为假如说n=0.001，那么它的三次方根应该=0.1超出了二分的范围


#include <iostream>
using namespace std;
int main(){
    double n;
    cin>>n;
    //为了防止x是小数的情况
    double l=-10000,r=10000;
    while(r-l>1e-8){
        double mid=(l+r)/2;
        if(mid*mid*mid<=n) l=mid;
        else r=mid;
    }
    //规定要保留6位小数
    printf("%.6f", r);
    return 0;
}

Leetcode034描述：

自己写的题解：

Leetcode034（在排序数组查找元素的第一个位置和最后一个位置）-------------二分法进阶（附带二种模板）_造船大学蒟蒻小菜鸡的博客-CSDN博客

Leetcode069（找平方根）：

题解地址：

Leetcode069（找平方根）---------二分法基础运用_造船大学蒟蒻小菜鸡的博客-CSDN博客

Leetcode074（搜索二维矩阵）：

单纯考察我们对于二分边界的掌握，以及一维坐标与二维坐标的转换直接上代码：


public boolean searchMatrix(int[][] matrix, int target) {
        //这题单纯考察我们对于二分边界的掌握，以及一维坐标与二维坐标的转换
        //先将二维转换为一维
        int row=matrix.length;//行数
        int rank=matrix[0].length;//列数
        int l=0,r=row*rank-1;
        while(l<r){
            int middle=l+r>>1;
            if(matrix[middle/rank][middle%rank]>=target)  r=middle;
            else l=middle+1;
        }
        if(matrix[l/rank][l%rank]==target) return true;
        else return false;
    }

Leetcode033、153(搜索旋转排序数组)----------二分法进阶

描述：

题解地址：

Leetcode033、153(搜索旋转排序数组)----------二分法进阶_造船大学蒟蒻小菜鸡的博客-CSDN博客

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/896680