小龙报个人主页作者简介C研发嵌入式机器人AI等方向学习者❄️个人专栏《优选算法》✨永远相信美好的事情即将发生文章目录前言一、搜索插入位置1.1题目1.2 算法原理1.2.1 算法思路1.3 代码二、x的平方根2.1 题目2.2 算法原理2.2.1 算法思路2.2.2 算法流程2.2.2.1 思路一暴力枚举2.2.2.2 思路二 二分查找2.3 代码总结与每日励志前言二分查找是算法笔试面试中的高频基础考点依托数组二段性可将时间复杂度优化至O(logN)高效解决有序数组检索问题。本文选取搜索插入位置、x的平方根两道经典入门例题拆解二分算法核心逻辑与边界处理技巧梳理不同场景下的解题思路帮助大家夯实二分思维掌握模板化解题方法为后续复杂算法学习筑牢基础。一、搜索插入位置1.1题目链接搜索插入位置1.2 算法原理核心思想:二分1.2.1 算法思路a. 分析插入位置左右两侧区间上元素的特点设插入位置的坐标为index根据插入位置的特点可以知道[left, index - 1]内的所有元素均是小于target的[index, right]内的所有元素均是大于等于target的。b. 设left为本轮查询的左边界right为本轮查询的右边界。根据mid位置元素的信息分析下一轮查询的区间当nums[mid] target时说明mid落在了[index, right]区间上mid左边包括mid本身可能是最终结果所以我们接下来查找的区间在[left, mid]上。因此更新right到mid位置继续查找。当nums[mid] target时说明mid落在了[left, index - 1]区间上mid右边但不包括mid本身可能是最终结果所以我们接下来查找的区间在[mid 1, right]上。因此更新left到mid 1的位置继续查找。c. 直到我们的查找区间的长度变为 1也就是left right的时候left或者right所在的位置就是我们要找的结果。1.3 代码classSolution{public:intsearchInsert(vectorintnums,inttarget){intl0,rnums.size()-1;while(lr){intmid(lr)/2;if(nums[mid]target)rmid;elselmid1;}if(nums[l]target)returnl1;elsereturnl;}};时间复杂度: O(n)二、x的平方根2.1 题目链接x的平方根2.2 算法原理核心思想二段性 -二分算法2.2.1 算法思路2.2.2 算法流程2.2.2.1 思路一暴力枚举依次枚举[0, x]之间的所有数i这里没有必要研究是否枚举到x / 2还是x / 2 1。因为我们找到结果之后直接就返回了往后的情况就不会再判断。反而研究枚举区间既耽误时间又可能出错如果i * i x直接返回x如果i * i x说明之前的一个数是结果返回i - 1。由于i * i可能超过int的最大值因此使用long long类型。设x的平方根的最终结果为index2.2.2.2 思路二 二分查找a. 分析index左右两次数据的特点[0, index]之间的元素平方之后都是小于等于x的[index 1, x]之间的元素平方之后都是大于x的。2.3 代码classSolution{public:intmySqrt(intx){if(x1)return0;longlongl1,rx;while(lr){longlongmid(lr1)/2;if(mid*midx)lmid;elsermid-1;}returnl;}};时间复杂度: OlogN总结与每日励志✨本文通过两道典型例题系统讲解了二分查找的核心原理区分了左右边界查找逻辑规避了数值溢出、区间死循环等常见bug梳理出通用解题模板。二分算法的核心在于精准判断区间二段性、灵活调整边界。算法学习没有捷径唯有坚持刷题、复盘总结不断打磨思维与细节突破解题瓶颈日积月累终会实现能力跃迁遇见更优秀的自己。