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