本篇会加入个人的所谓<code>鱼式疯言

❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言

而是理解过并总结出来通俗易懂的大白话,

小编会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的.

🤭🤭🤭可能说的不是那么严谨.但小编初心是能让更多人能接受我们这个概念 ！！！

前言

在前面的章节中，我们学习了 "双指针"算法 ， “滑动窗口"算法

而在本篇章节 ， 我们期待已久的 “二分查找”算法 即将登场， 透露下本次算法主要的规划 💖 💖 💖

目录

二分算法的初识

二分算法的应用

二分算法的总结

一. 二分算法的初识

1. 二分算法的简介

二分算法，也被称为 二分查找 算法，是一种常用的<code>查找 算法。

它的基本思想是将已排序的数据序列分成 两部分 ，取中间 的元素与 目标值 进行比较，然后根据比较结果，确定目标值 在左半部分还是 右半部分，再继续在相应的部分进行 查找，直到找到目标值或者确定目标值 不存在 为止。

2. 二分算法的使用步骤

因为二分查找算法分为两种：

“一种是 朴素二分查找” 算法， 另外一种是 "左右边界二分查找 " 算法

因为朴素二分查找比较基础，我们先学习基础版本的，再调整有难度的 💖 💖 💖

小编在这里说明 “朴素二分查找” 的具体步骤哦

先拿个题目来瞧瞧呗

二分查找

704.二分查找题目链接

<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

题目含义

在给定的数组中查找一个数 ，返回其 下标 ，如果没有就返回 <code>-1

<2>. 讲解算法思想

题目分析 ： 我们要查找一个数最简单的方式

解法一 ：

暴力求解

用一个 for -遍历 数组 ，然后中间用一个 if 来判断 ，一定成立就返回其下标

在解法一的基础上，我们为了减少一半的数据，特别提炼出 二分查找 算法的思想

解法二 ：

二分算法 :

首先，确定要查找的目标值在序列中的可能范围，通常是通过比较目标值和序列的 第一个元素 和 最后一个元素 来确定；

我们定义 一个数组的第一个元素的为 <code>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;

}

}

鱼式疯言

朴素二分的算法体会就是

<code>小了 整体新的区间移动到 中间值的右边

大了 整体新的区间移动到 中间值的左边

并且 朴素二分 必须是保证数据是有序的

while(left <= right) { };

细节注意

我们需要这里要取等的， 当 left 和 right 相等 的时候， 也有可能是 目标值

二. 二分算法的应用

讲解完了 朴素的二分算法， 接下来讲解了 左右边界二分查找 算法

小编在这里说一句哦，这个 左右边界的 二分算法思想

可以这么说，是 基础算法 细节最多，最恶心 ，也是 最容易造成死循环 的一种算法

1. 寻找峰值

162.寻找峰值题目链接

<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。

题目含义 :

在一个数组寻找一个既 <code>小于左边 又 小于右边 的 一个数字的 下标值

<2>. 讲解算法思想

其实本质上我们可以认为是寻找一个 极大值(也可以是最大值)

解法一 :

暴力遍历 :

我们只需要遍历数组即可查找到我们 极大值

解法二 :

二分算法

当我们需要寻找一个 最大值 的 时候， 我们可以通过 单调性 来寻找 二段性

什么是 二段性 ， 就是在数组中可以区分为 两个区域 ，我们可以把这个区域划分为 两段 ，而这个 两端 我们可以进行分为

第一个区域的 右边界 ，以及相邻的第二个区域的 左边界

首先我们定义 left 为 第一个元素 下标 ， right 为 最后 一个元素下标

如果 mid 在 递增 区间， 就让 left = mid

如果 mid 在 递减 区间， 就让 right = mid - 1 ；

最后就是我们需要注意的就是 终止条件 怎么设置

当 递减区间 边界的 right 刚好跳到 左边 ，而 left 也刚刚好处于 递增区间 的时我们就可以确定右边界了

所以我们 只需要让 left 等于 right

<3>. 编写代码

<code>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;

}

}

鱼式疯言

小编的体会

对于二分算法来说，<code>二段性 才是 核心 , 如何寻找到在 一个区间 中划分为 两个 不同含义 的区间，

从而利用二分法寻找左右边界来得到目标值

本题寻找二段性 常见的方式: 递增性…

细节处理:

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]

题目含义 :

寻找一段相同目标值的 <code>第一个位置 和 最后一个位置 的 下标

<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] 上寻找 左边界；

当我们需要右边界时

按照上面我们寻找 左边界 的思维来寻找 <code>右边界

我们就以 右边界 的来划分区域

当 mid 处于 <= target 时 ，right = mid；

当 mid 处于 > target 时 ， left = mid -1；

<3>. 编写代码

<code>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;

}

}

鱼式疯言

说下对于本题小编个人的体会吧

二段性 我们是找到了，但这里的是如何去 划分我们的区域

所以然后选择 <code>等号 也是很关键的一条

当我们寻找 左边界 时，我们就需要 让 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 次得到输入数组。

** 题目含义** ：

在一个由原先 <code>有序 进行 旋转 后的数组中，寻找 最小值

<2>. 讲解算法思想

题目分析

因为题目要求时间 复杂度只能是 O(log n)

所以这样我们就需要用到 二分算法

那我们就必须寻找到 二段性

首先还是利用的大小关系来寻找我们的 基准值

因为是 反转后的数据，所以从最小值到最后一个元素必然是 递增 的，

那么这段区间肯定都是 小于等于 最后一个元素的

而 翻转过去的元素 必然是 <code>大于 我们最后一个元素的，我们又划分出了 这段区间

** 二分算法**

所以我们操作数字定义 left= 0 ，right 指向最后一个元素 ， 并且取一个 基准值 target 也为最后一个元素

然后进行 mid 的判断，以及 right 和 left 的移动,

最终 left 和 right 相遇的位置就是我们要找的 最小值

<2>.编写代码

<code>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];

}

}

三. 二分算法的总结

我们先初步认识了什么是 二分算法以及并明白了 朴素二分查找算法 的使用，

并且 朴素 是在 有序 的条件下进行

之后我们又通过 <code>“寻找峰值”，“在排序数组中查找元素中 第一个位置和最后一个位置”，"寻找排序数组中的最小值" , 我们更明白 寻找 二段性 比如通过 比大小, 单调性， 端点值, 不等性

下面有 小彩蛋哦

总结朴素二分算法模板

总结左右边界二分算法模板

记住一点：

求左边界时： right = mid

求右边界时： left = mid

如果觉得小编写的还不错的咱可支持 三连 下 (定有回访哦) , 不妥当的咱请评论区 指正

希望我的文章能给各位宝子们带来哪怕一点点的收获就是 小编创作 的最大 动力 💖 💖 💖