查找算法搜索二分法（python）

见贤思齐

Hi，大家好，我是半亩花海。近期在学习算法与数据结构相关知识，纯纯小白，欢迎一起交流呀。打算从算法学起，首先学习查找算法（搜索）中的二分法，我使用的是python语言进行学习。本算法学习参考了很多博主的文章，比如：算法第三期——二分法（Python）_python二分法-CSDN博客、玩转二分法（python版）——leetcode二分法题总结【简单易懂】_len(nums)-1-CSDN博客、Python实现二分法搜索_二分法python-CSDN博客 以及LeetCode等等。目录一、二分法概述1.1理论背景：非线性方程的求根问题1.2使用条件1.3复杂度分析二、二分法求解方法2.1基本思想2.2代码模板2.2.1闭区间：[left,right]2.2.2左闭右开区间：[left,right)2.2.3开区间：(left,right)三、二分法例题1.LeetCode[704.二分查找]【简单】方法一：暴力法方法二：二分查找法2. LeetCode[69.x的平方根]【简单】方法：二分查找法3.LeetCode[35.搜索插入位置]【简单】方法：二分查找法4.LeetCode[34.在排序数组中查找元素的第一个和最后一个位置]【中等】方法一：暴力法方法二：二分查找法 一、二分法概述在一个有序序列中查找某个元素，在之前我们可以使用暴力法来遍历序列，直至找到该元素，复杂度是 ，但其实可以利用序列有序的特征进行折半查找。二分法定义：把一个长度为的有序序列上 的查找时间，优化到了 。二分法本质：折半搜索。二分法效率：很高，时间复杂度为 （其实不太严谨，因为需要考虑底数，那就要看分治的复杂度：二分法底数为2，则为复杂度为  ；三分法底数为3，则为 ...以此类推。当然不写底数也行，但是得知道它有底数）。二分法实例——猜数游戏：若  万，只需要猜  次。1.1理论背景：非线性方程的求根问题满足方程： 的数  称为方程的根。非线性方程：指 中含有三角函数、指数函数或其他超越函数。很难或者无法求得精确解。二分法是一种求解的方法。1.2使用条件上下界[a,b]确定函数在[a,b]内单调1.3复杂度分析 次二分后，区间缩小到 给定  和精度要求 ，可以算出二分次数 ，即满足： 二分法的复杂度：时间复杂度： ，其中是数组的长度。空间复杂度： 示例：如果函数在区间 内单调变化，要求根的精度是，那么二分次数是44次。因为：二、二分法求解方法2.1基本思想首先把循环可以进行的条件写成whileleft=target的i如果数组为空，或者所有数都小于target，则返回len(nums)要求nums是非递减的，即nums[i]=targetmid=(left+right)//2ifnums[mid]=targetmid=(left+right)//2ifnums[mid]int:left,right=-1,len(nums)#开区间(left,right)whileleft+1=targetifnums[mid]target:right=mid-1else:left=mid+1return-1#search=BinarySearch()#nums=[-1,0,3,5,9,12]#target=9#print(search.binary_search(nums,target))#输出：42. LeetCode[69.x的平方根]【简单】题目：给你一个非负整数，计算并返回 的 算术平方根 。由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。注意：不允许使用任何内置指数函数和算符，例如  或者  。示例1：输入：x=4输出：2示例2：输入：x=8输出：2解释：8的算术平方根是2.82842...,由于返回类型是整数，小数部分将被舍去。思路及题解：方法：二分查找法（1）思路由于 平方根的整数部分 是满足  的最大 值，因此我们可以对 进行二分查找，从而得到答案。二分查找的下界为，上界可以粗略地设定为。在二分查找的每一步中，我们只需要比较中间元素 的平方与 的大小关系，并通过比较的结果调整上下界的范围。由于我们所有的运算都是整数运算，不会存在误差，因此在得到最终的答案  后，也就不需要再去尝试 了。（2）题解classSolution(object):defmySqrt(self,x):left,right,ans=0,x,-1whileleft=target:r=midelse:l=mid+1ifnotnumsornums[l]!=target:#数组为空或没找到return[-1,-1]a,b=l,len(nums)-1#取结束下标whilea