专题三：二分查找

二分法的使用在于对参照数据二段性的抽象划分。细节问题细节问题的产生原因数组边界划分为两段区域其中一个包含目标另外一个是舍弃区域。当以mid ± i (i 0/1) 赋值l、r时l、r的尽量移动。mid更新时若减则加。模板一while(l r) //此处一定是l r为什么二分下的mid ± 1 { int mid l (r - l)/2; if(…………) l mid 1; else if(…………) r mid - 1; else return mid; }模板二while(l r) { int mid l (r - l)/2; if(…………) r mid; else l mid 1; }模板三while(l r) { int mid l (r - l 1)/2; if(…………) l mid; else r mid - 1; }1.二分查找(easy)循环结束的条件left right怎么推断的不严谨的分析方法要么是left right 要么是 left right严谨的分析方法 在left与right维护的区间内数据未知所以是left right可不可能导致5 5 而一直5呢不会。因为在逻辑优化下l mid 1 或者 r mid - 1在对于奇数个数组元素的mid划分会不会导致什么问题不会。 核心在于在[mid] ! target 时 l mid 1或r mid - 1逻辑优化点mid l - (l/2 - r/2);题目详情给定一个n个元素有序的升序整型数组nums和一个目标值target写一个函数搜索nums中的target如果target存在返回下标否则返回-1。你必须编写一个具有O(log n)时间复杂度的算法。示例 1:输入:nums [-1,0,3,5,9,12], target 9输出:4解释:9 出现在 nums 中并且下标为 42.在排序数组中查找元素的起始和末尾位置(normal)使用左右依次查找端点位置给你一个按照非递减顺序排列的整数数组nums和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值target返回[-1, -1]。你必须设计并实现时间复杂度为O(log n)的算法解决此问题。示例 1输入nums [5,7,7,8,8,10], target 8输出[3,4]3.x的平方根(easy)给你一个非负整数x计算并返回x的算术平方根。由于返回类型是整数结果只保留整数部分小数部分将被舍去 。注意不允许使用任何内置指数函数和算符例如pow(x, 0.5)或者x ** 0.5。示例 1输入x 4输出24.搜索插入位置(easy)给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。请必须使用时间复杂度为O(log n)的算法。输入:nums [1,3,5,6], target 2输出:15.山峰数组的元素索引(normal)nums[mid] nums[mid1] l mid1;给定一个长度为n的整数山脉数组arr其中的值递增到一个峰值元素然后递减。返回峰值元素的下标。你必须设计并实现时间复杂度为O(log(n))的解决方案。输入arr [0,10,5,2]输出16.寻找任一峰值(normal)峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组nums找到峰值元素并返回其索引。数组可能包含多个峰值在这种情况下返回任何一个峰值所在位置即可。你可以假设nums[-1] nums[n] -∞。你必须实现时间复杂度为O(log n)的算法来解决此问题。输入nums [1,2,1,3,5,6,4]输出1 或 5解释你的函数可以返回索引 1其峰值元素为 2 或者返回索引 5 其峰值元素为 6。7.寻找旋转排序数组中的最小值(normal)定点参考已知一个长度为n的数组预先按照升序排列经由1到n次旋转后得到输入数组。例如原数组nums [0,1,2,4,5,6,7]在变化后可能得到若旋转4次则可以得到[4,5,6,7,0,1,2]若旋转7次则可以得到[0,1,2,4,5,6,7]注意数组[a[0], a[1], a[2], ..., a[n-1]]旋转一次的结果为数组[a[n-1], a[0], a[1], a[2], ..., a[n-2]]。给你一个元素值互不相同的数组nums它原来是一个升序排列的数组并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。你必须设计一个时间复杂度为O(log n)的算法解决此问题。输入nums [3,4,5,1,2]输出1解释原数组为 [1,2,3,4,5] 旋转 3 次得到输入数组。思路堵塞具体体现为无法判断r的移动依据思路堵塞的原因简图画错 未利用旋转的关键值。后来通过演示实例发现可以以nums[0]为标杆对比[mid]来进行移动bug分析if(nums[mid] nums[0]) l mid 1; // mid的位置可能是0导致相等而造成r的移动else r mid;产生bug的原因特殊标记位08.找到0~n-1中不连续数(easy)参照为mid - 0与 [mid]的关系多种方法bug分析相对位置 当l r 0时若是学号0缺失则返回1 示意图如下某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组records。假定仅有一位同学缺席请返回他的学号。输入records [0, 1, 2, 3, 4, 5, 6, 8]输出7