阅读量:3
本篇会加入个人的所谓鱼式疯言
❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言
而是理解过并总结出来通俗易懂的大白话,
小编会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的.
🤭🤭🤭可能说的不是那么严谨.但小编初心是能让更多人能接受我们这个概念 ！！！
前言
在前面的章节中，我们学习了 "双指针"算法 ， “滑动窗口"算法
而在本篇章节 ， 我们期待已久的 “二分查找”算法 即将登场， 透露下本次算法主要的规划 💖 💖 💖
目录
二分算法的初识
二分算法的应用
二分算法的总结
一. 二分算法的初识
1. 二分算法的简介
二分算法，也被称为 二分查找 算法，是一种常用的查找 算法。
它的基本思想是将已排序的数据序列分成 两部分 ，取中间 的元素与 目标值 进行比较，然后根据比较结果，确定目标值 在左半部分还是 右半部分，再继续在相应的部分进行 查找，直到找到目标值或者确定目标值 不存在 为止。
2. 二分算法的使用步骤
因为二分查找算法分为两种：
“一种是 朴素二分查找” 算法， 另外一种是 "左右边界二分查找 " 算法
因为朴素二分查找比较基础，我们先学习基础版本的，再调整有难度的 💖 💖 💖
小编在这里说明 “朴素二分查找” 的具体步骤哦
先拿个题目来瞧瞧呗
二分查找
<1>. 题目描述
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
题目含义
在给定的数组中查找一个数 ，返回其 下标 ，如果没有就返回 -1
<2>. 讲解算法思想
题目分析 ： 我们要查找一个数最简单的方式
解法一 ：
暴力求解
用一个 for-遍历 数组 ，然后中间用一个 if 来判断 ，一定成立就返回其下标
在解法一的基础上，我们为了减少一半的数据，特别提炼出 二分查找 算法的思想
解法二 ：
二分算法 :
- 首先，确定要查找的目标值在序列中的可能范围，通常是通过比较目标值和序列的 第一个元素 和 最后一个元素 来确定；
我们定义 一个数组的第一个元素的为 left ， 再定义 最后一个元素 的下标为 right
然后，在可能范围内，取中间的元素与目标值进行比较；
如果中间的元素等于目标值，则查找成功，返回对应的位置；
如果中间的元素
大于目标值，则说明目标值可能在 左半部分 ，缩小范围到左半部分继续查找，重复步骤2；如果中间的元素
小于目标值，则说明目标值可能在 右半部分 ，缩小范围到右半部分继续查找，重复步骤2；如果范围缩小到只有一个元素，但该元素不等于目标值，则查找失败，目标值不存在。
二分算法的时间复杂度为 O(log n) ，其中
n是序列的长度。``二分算法通常适用于 已排序的数据序列，能够快速查找目标值的位置。
<3>. 编写代码
class Solution { public int search(int[] nums, int target) { int numslen = nums.length; int left=0,right=numslen-1; while(left <= right) { int mid= left + ((right - left) >>> 1); if(nums[mid] > target) { right = mid - 1; } else if(nums[mid] < target ) { left = mid + 1; } else { return mid; } } return -1; } } 
鱼式疯言
朴素二分的算法体会就是
小了整体新的区间移动到中间值的右边
大了整体新的区间移动到中间值的左边
并且
朴素二分必须是保证数据是有序的
while(left <= right) {}; 细节注意
我们需要这里要取等的， 当 left 和 right相等 的时候， 也有可能是 目标值
二. 二分算法的应用
讲解完了 朴素的二分算法， 接下来讲解了 左右边界二分查找 算法
小编在这里说一句哦，这个 左右边界的 二分算法思想
可以这么说，是 基础算法 细节最多，最恶心 ，也是 最容易造成死循环 的一种算法
1. 寻找峰值
<1>. 题目描述
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
示例 1：
输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。
示例 2：
输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5， 其峰值元素为 6。
题目含义 :
在一个数组寻找一个既 小于左边 又 小于右边 的 一个数字的 下标值
<2>. 讲解算法思想
其实本质上我们可以认为是寻找一个 极大值(也可以是最大值)
解法一 :
暴力遍历 :
我们只需要遍历数组即可查找到我们 极大值
解法二 :
二分算法
当我们需要寻找一个 最大值 的 时候， 我们可以通过 单调性 来寻找 二段性
什么是 二段性 ， 就是在数组中可以区分为 两个区域 ，我们可以把这个区域划分为 两段 ，而这个 两端 我们可以进行分为
第一个区域的 右边界 ，以及相邻的第二个区域的 左边界
- 首先我们定义 left 为
第一个元素下标 ， right 为最后 一个元素下标
- 如果
mid在 递增 区间， 就让 left = mid
- 如果
mid在 递减 区间， 就让 right = mid - 1 ；
- 最后就是我们需要注意的就是 终止条件 怎么设置
- 当 递减区间 边界的
right刚好跳到 左边 ，而left也刚刚好处于递增区间的时我们就可以确定右边界了
所以我们 只需要让
left等于right
<3>. 编写代码
class Solution { public int findPeakElement(int[] nums) { // 进行 左二分查找算法 int left=0,right=nums.length-1; while(left < right) { int mid= left + ( (right - left + 1) >>> 1 ); if(nums[mid] > nums[mid-1]) { left = mid; } else { right = mid -1; } } return right; } } 
鱼式疯言
小编的体会
- 对于二分算法来说，
二段性才是 核心 , 如何寻找到在一个区间中划分为两个不同含义 的区间，
从而利用二分法寻找左右边界来得到目标值
本题寻找二段性 常见的方式: 递增性…
细节处理:
int mid= left + ( (right - left + 1) >>> 1 ); 这里我们需要用到 当我们用到 right = mid - 1 ;
自然我们就需要 在这里进行 +1 操作
2. 在排序数组中查找元素中 第一个位置和最后一个位置
<1>. 题目描述
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
题目含义 :
寻找一段相同目标值的 第一个位置 和 最后一个位置 的 下标
<2>. 讲解算法思想
题目分析:
用的还是二分思想，就是根据数据的性质，在某种判断条件下将区间 一分为二 ，然后舍去其中一个
区间，然后再另一个区间内查找；方便叙述，用 target 表示该元素， left 表示 左边界， right 表示右边界。
当我们求左边界时， 就可以按照
寻找左边界：
我们注意到以左边界划分的两个区间的特点：
左边区间 [left, left - 1] 都是小于 target 的；
右边区间（包括左边界） =[left, right] 都是 大于等于 x 的；
因此，关于 mid 的落点，我们可以分为下面两种情况：
当我们的
mid落在[left, left - 1]区间的时候，也就是 arr[mid] <
target 。说明
[left, mid]都是可以舍去的，此时更新left到mid + 1的位置，
继续在 [mid + 1, right] 上寻找左边界；当 mid 落在 [left， right] 的区间的时候，也就是 arr[mid] >= target 。
说明 [mid + 1, right] （因为 mid 可能是最终结果，不能舍去）是可以舍去的，此时
更新right到mid的位置，继续在 [left, mid] 上寻找 左边界；
当我们需要右边界时
按照上面我们寻找 左边界 的思维来寻找 右边界
我们就以 右边界 的来划分区域
当 mid 处于 <= target 时 ，right = mid；
当 mid 处于 > target 时 ， left = mid -1；
<3>. 编写代码
class Solution { public int[] searchRange(int[] nums, int target) { // 定义一个存放起始和终止位置的数组 int[] ret=new int[]{-1,-1}; // 得到长度 int len=nums.length; // 数组为 空 时 就直接返回 if(len == 0) return ret; // 进行二分操作 // 定义左右指针 int left=0,right= len-1; /** * 寻找左边界 * 当 right = mid = left 就会陷入死循环 * 细节一 : 终止条件 不能写等号 * * 当 中点值 <= target 时 * 细节二 ： 我们更新 left = mid * * 当 left mid right 相邻 时 * 细节三 ： 更新 mid = left + ( (right - left + 1) >>> 1 ) * */ // while(left < right) { int mid=left + ( (right-left) >>> 1); if(nums[mid] < target) { left = mid+1; } else if(nums[mid] >= target) { right = mid ; } } if(nums[right] == target) ret[0] = right; left=0; right=len-1; /** * 寻找右边界 * * 当 right = mid = left 就会陷入死循环 * 细节一 : 循环终止条件 ： 这里不可以进行 取等 * * 当 中点值 >= target 时 进行 right 移动 * 细节二 : 右指针 right 移动的位置 是 到达 中点下标 mid * * * left mid right * 当 中点 和 left right 相邻 时就需要 * 细节三 : 确立 mid = left +( (right - left ) >>> 1 ) */ while(left < right) { int flg=left + ( (right - left + 1) >>> 1); if(nums[flg] <= target) { left = flg; } else if(nums[flg] > target) { right = flg -1; } } if (nums[left]== target) ret[1]= left; return ret; } } 
鱼式疯言
说下对于本题小编个人的体会吧
二段性 我们是找到了，但这里的是如何去 划分我们的区域
所以然后选择 等号 也是很关键的一条
当我们寻找 左边界 时，我们就需要 让 mid >= target 的情况进行划分
当我们寻找 右边界 时， 我们就需要 让 mid < target 的情况进行划分\
细节处理
处理 右边界 的时
while(left < right) {} 当 right = mid = left 就会陷入
死循环
细节一 :
终止条件 不能写等号
if(nums[flg] <= target) { left = flg; } 当
中点值 <= target时
细节二 ：
我们更新 left = mid
当
left mid right相邻 时
细节三 ：
更新 mid = left + ( (right - left + 1) >>> 1 )
处理 左边界 时
while(left < right) {} 当 right = mid = left 就会陷入
死循环
细节一 :
终止条件 不能写等号
if(nums[flg] >= target) { right = flg; } 当 中点值 <= target 时
细节二 ：
我们更新 right = mid
当
left mid right相邻 时
细节三 ：
更新 mid = left + ( (right - left ) >>> 1 )
3. 寻找排序数组中的最小值
<1>. 题目描述
已知一个长度为 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) 的算法解决此问题。
示例 1：
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 3 次得到输入数组。
示例 3：
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
** 题目含义** ：
在一个由原先 有序 进行 旋转 后的数组中，寻找 最小值
<2>. 讲解算法思想
题目分析
因为题目要求时间 复杂度只能是 O(log n)
所以这样我们就需要用到 二分算法
那我们就必须寻找到 二段性
首先还是利用的大小关系来寻找我们的 基准值
因为是 反转后的数据，所以从最小值到最后一个元素必然是 递增 的，
那么这段区间肯定都是 小于等于 最后一个元素的
而 翻转过去的元素 必然是 大于 我们最后一个元素的，我们又划分出了 这段区间
** 二分算法**
所以我们操作数字定义 left= 0 ，right 指向最后一个元素 ， 并且取一个 基准值 target 也为最后一个元素
然后进行 mid 的判断，以及 right 和 left 的移动,
最终 left 和 right 相遇的位置就是我们要找的 最小值
<2>.编写代码
class Solution { public int findMin(int[] nums) { // 进行二分左查找 int left= 0, right=nums.length-1; // 以 最右边为基准值 进行 原数组的划分 int flg=nums[right]; while(left < right) { // 得到中间 下标 int mid= left + ( (right - left ) >>> 1 ); // 如果 小于 基准 说明 是 左边的数 ， 不存在最小值 if( nums[mid] > flg) { left = mid +1; } else { // 存在 右边 小于或等于 基准值 right =mid; } } return nums[left]; } } 
三. 二分算法的总结
我们先初步认识了什么是 二分算法以及并明白了 朴素二分查找算法 的使用，
并且 朴素 是在 有序 的条件下进行
之后我们又通过 “寻找峰值”，“在排序数组中查找元素中 第一个位置和最后一个位置”，"寻找排序数组中的最小值" , 我们更明白 寻找 二段性 比如通过 比大小, 单调性， 端点值, 不等性
下面有 小彩蛋哦
总结朴素二分算法模板
总结左右边界二分算法模板
记住一点：
求左边界时： right = mid
求右边界时： left = mid
如果觉得小编写的还不错的咱可支持 三连 下 (定有回访哦) , 不妥当的咱请评论区 指正
希望我的文章能给各位宝子们带来哪怕一点点的收获就是 小编创作 的最大 动力 💖 💖 💖
