广州网站定制开发,闪图在线制作网站,上海企业名称,国内新闻最新二分查找 题目描述 题目解析 暴力解法 我们可以从左往右遍历一次数组#xff0c;如果存在 target 则返回数组的下标#xff0c;否则返回 -1#xff1b;
时间复杂度 O(N)#xff0c;因为没有利用数组有序的特点#xff0c;每次比较只能舍弃一个要比较的数如果存在 target 则返回数组的下标否则返回 -1
时间复杂度 O(N)因为没有利用数组有序的特点每次比较只能舍弃一个要比较的数 二分查找法 所以我们可以把 [1 , 4 ] 这个区间舍弃掉直接看 [ 5 , 8 ]仅仅拿 4 和 5 比较一次就干掉了一大片数 总结 在一个数组中随便找一个数拿这个数和 target 进行比较并且以拿的这个数分成两个区间比较后舍弃一部分数然后再从另一个区间的数中找下一个要和 target 比较的数 二分查找算法的本质就是当数组具有“二段性”时哪怕这个数组是无序的只要能在这个数组中发现“二段性”那么也可以使用二分查找 “二段性” 当我们发现一个规律然后根据这个规律选取某一个点根据这个点能把数组分成两个区域根据规律能够有选择地舍弃一部分进而在另一个部分继续查找的时候此时就可以使用二分查找的算法 我们要从数组中找和 target 进行比较的数不一定是先从 n/2 的位置开始找只要找的这个数的点能把这个区间分成两部分即满足二段性进而使用二分查找法
但是哪怕那么多点可以选择但是我们都应该先选择 n/2 的位置的点因为在概率学的数学期望中我们选择中间的点时间复杂度是最好的 nums[mid] targetleft mid1nums[mid] targetreturn midnums[mid] targetright mid-1 细节问题 因为当 left right 的时候也是要继续判断的所以 left right 为循环判断条件
时间复杂度只需要看循环执行多少次 如何求 x 呢 int mid (left right) / 2mid 会有溢出风险 如果想不从 n/2 开始查找可以修改如下面的写法是从 n/3 开始查找的 在排序数组中查找元素的第一个和最后一个位置 题目解析 发现二段性 方法一利用数组有序特性使用简单的二分查找法 如果使用简单的二分查找创建左指针和右指针再找中间值对这个中间值分别进行讨论如果对于一些特点的情况如下面的这种情况这个方法的时间复杂度会非常高 虽然 mid 指针刚好指向 target但是不能确定此时的 mid 指向的是在目标连续区域的哪一个位置从而不好找目标区域的起始位置和终点位置
所以使用简单二分查找的方法对于上述情况和类似情况查找的时间复杂度会近似于暴力查找 方法二在简单二分查找方法的基础上对二分策略进行优化 回到题目的规律当发现题目具有二段性就可以利用二分查找 因为不能同时查找目标区间起始位置和终点位置所以我们可以先查找起始位置 利用二段性我们可以根据目标值起始位置把数组区间分成两个部分 左边区域的值都是小于 target右边区域的值都大于等于target根据 target在查询目标区域左端点的时候发现这个数组是有二段性因此可以使用二分查找 查找区间左端点 以 mid 的值来决定 left 和 right 的更新方法 我们设 mid 指向的值为 x我们要找 target 区间的起始位置拿 x 的值与 target 讨论 1. x target此时 mid 落在 target 的区域不可能有最终结果所以继续往下执行 2. x target (不同点之前简单二分查找的方法分三种情况讨论这里只分两种情况因为 x target 并不是最终的结果因为最终的结果的左端点和右端点) 对于这种情况对应的做法 我们虽然[mid , right] 区间的情况一定是都大于 target但是不知道 [left , mid] 区间的具体情况是都小于 target 还是部分小于 target所以 right 绝对不能移动到 [left , mid] 这个不确定的区间因为如果 mid 在修改之前就是目标区间的左端点让 right mid -1[left , right]这个区间就没有 target 了所以 right mid 即可 处理细节问题 1.循环条件 对于执行循环操作二分查找操作的第一个循环条件是 left right还是 left right 呢 一定是选择 left right 为什么呢有两个原因 原因一因为 left right 的情况不需要放到循环中判断
我们分三种情况来讨论ret 为返回的最终结果 1. 数组中有元素等于 target 前面提到left 刚开始一直处于 target 的区间在 x target 的条件下rightmid所以right 一定在 ret 右边的区间threshold 为ret 第一个 target 元素的前一个元素 因为 left 和 right 的调整方式是 left mid1right mid所以 right 一直在 target 的区域移动而 left mid 1说明 left 是一直想要跳出 target 的区域的 所以当 left 和 right 调整到最后循环结束此时 left 一定会和 right 相等此时我们在循环结束后单独判断相遇点和 target 是否相等即可如果 left right 那么两个指针指向的位置一定就是目标区间左端点 ret所以循环条件只需要判断 left right 即可 2. 数组中所有元素全都大于 target 如果所有数组元素都大于 target那么整个过程只有 right 指针在不断向左边移动直到 left 和 right 相遇 哪怕相遇也没有最终结果所以这种情况下我们只需要在left right 时执行循环循环退出leftright 此时我们只需要拿当前两个指针指向的值和 target 比较相同则回到第一种情况这个值就是目标区间的左端点不相同则返回 [-1,-1] 3. 数组中所有元素全都小于 target 这种情况和第二种情况同理 整个更新过程都只有 left 在移动循环退出时left right只需要判断当前指针的值和 target 是否相等即可相等则这个值就是目标区域的起始位置 ret否则返回 [-1,-1] 原因二如果在循环条件中判断 left right会出现死循环 什么时候会出现死循环就是整个数组中有元素等于 target 的时候 如果循环条件是 while(left right){ ..... }此时left right 更新的 mid还是指向 leftright 所在位置此时满足 x target 条件rightmid所以 right leftleft 和 right 就会一直停在一个地方循环更新结果这种情况下就会出现死循环 2. 求中点操作 求中点操作也就是在定义 left 和 right 之后求 mid 的操作 1. mid left ( right - left ) / 2 ; 2. mid left ( right - left 1 ) /2 ; 这两种求中点的操作区别在于数组元素是偶数时更新 mid 的位置不同这两种方法在简单二分情况如第一题的情况都是可以用的但是这种情况下不能用 mid left (right - left 1)/2 求中点 如果是用第二种方法 mid left (right - left 1)/2此时 mid 的位置 如果上图条件中target 3那么此时 mid target left mid1程序结束此时是没问题的 但是如果 target 3那么此时 midtarget此时调整 right mid就又进入死循环了 所以在求左端点时只能用 mid left (right - left )/2 来求中点 查找区间右端点 根据查找右端点依旧可以把整个区间分成两部分targettarget : 根据 mid 与 target 的关系决定更新操作 1. x target 因为我们要保证在调整 left 和 right 的过程中右端点一定要在 [leftright] 区间所以当前这种情况我们应该移动 left 2. x target 因为 x target所以mid 所在位置一定是在目标区域之外因此更新 right mid -1 处理细节问题 1. 循环条件 2. 求中点的操作 循环条件和求左端点相同不同的是求中点的公式 1. mid left ( right - left ) / 2 ; 2. mid left ( right - left 1 ) /2 ; 这两种求中点的操作区别在于数组元素是偶数时更新 mid 的位置不同这两种方法在简单二分情况如第一题的情况都是可以用的但是这种情况下不能用 mid left (right - left )/2 求中点 为了接下来的操作不和求左端点的时候弄混要牢记此时要求的是右端点接下来的假设都是为了能求出右端点 如果是用第二种方法 mid left (right - left )/2此时 mid 的位置 如果上图条件中target 2那么此时 mid target right mid-1程序结束此时是没问题的 但是如果 target 3那么此时 midtarget此时调整 left mid就又进入死循环了 所以在求右端点时只能用 mid left (right - left 1 )/2 来求中点在求右端点时为什么用这条公式求中点不会出现死循环呢 用 mid left (right - left 1 )/2 来求中点此时 mid 在 right 的位置如果此时 x targetrightmid-1此时不满足 leftright 的条件会结束循环如果 x targetleft mid : 此时也不满足 leftright 的条件也会结束循环所以在求右端点的时候用 mid left (right - left 1)/2 来求中点就不会出现死循环 编写代码 总结二分模板
