二分查找实战：LeetCode样题精解

1.lecode例题：https://leetcode.cn/problems/binary-search/solutions/980494/er-fen-cha-zhao-by-leetcode-solution-f0xw

2.解题思路：

找到target并返回target的索引下标，想用bisect二分。首先理解bisect的语法，给定一个单调不减的有序数组a，返回恰好严格大于x的下标位置。但这里有所区别，题目要求是刚好等于target的位置，所以我想用bisect变形。即题目转化为敲好大于等于target的下标位置，输入bisect（a，target-1） 刚开始我还输入了nums n m Q等数据输入板块，第一次做lecode题库，初尝新，知道了lecode不需要数据输入模块，前面两行代码是平台预设的框架，用户只需关注算法本身逻辑

3.过程错误与修正：

a.过程错误 (前三行快读模板熟练敲打)

b.错误分析解读（two methods）

1.from bisect import * 对应index=bisect_left(nums,target) 【既然菜都在桌子上了直接开吃，不用＋bisect餐厅名】

2.import bisect 对应 index=bisect.bisect_left(nums,target) 【先进入餐厅再点菜引bisect再bisect.left】

[通俗理解：bisect是一个餐厅，bisect_left~bisect_right~是bisect餐厅里的菜品名，输入1.时相当于叫服务员把所有菜品都上，再输入bisect.bisect_left相当于把餐厅都叫上来了但是餐厅不是菜品故报错，当输入bisect.bisect_left时相当于在糖醋排骨里找回锅肉，这怎么可能故报错了]

4.官网样题学习（知二分底层思维逻辑）

len（nums）-1：索引值比len少1

mid=（right-left）//2+left：确定不断更新的mid位置（相对位置and绝对位置区分）

{如l=2，r=6，r-l=4//2=2，此时mid=2+l（2）=4}

二分思维逻辑透析：

a.定左右区间（r=len-1）查找整个数组

b.不断更新左右区间和mid

c.if判断不断更新的mid与target的关系（mid>t:right=mid-1；mid<t：left=mid+1）

5.二分变形（bisect二分）

学习资源：bilibili up主TsingPing

a.基础模型：给定一个单调不减有序数组a，bisect（a，x），返回大于x的索引

b.变型  *大于等于x=大于x-1    bisect（a，x-1）

             *小于等于x=大于x的索引-1   bisect（a，x）-1

             *给定一个单调不增数组a，转变为单调不减数组-a  a=[-x for x in a]  bisect（a，-x）

              （镜像对称）

6.解题策略与提升

好吧我现在理解了但是当再次做到这种类似二分，我将背硬套模板

普通二分标准代码如上4（1）图