wdcp 网站备份,公司网站域名解析谁来做,北京app定制公司,网站的首屏 一屏 二屏是什么意思文章目录 前言核心问题遍历查找思路遍历查找代码实现遍历查找缺点二分查找思路二分查找代码实现二分查找优点二分查找的变种问题一解题思路代码实现问题二解题思路代码实现 前言
大家好#xff0c;我是醉墨居士#xff0c;今天聊一下计算机中的经典算法 - 二分算法
核心问题… 文章目录 前言核心问题遍历查找思路遍历查找代码实现遍历查找缺点二分查找思路二分查找代码实现二分查找优点二分查找的变种问题一解题思路代码实现问题二解题思路代码实现 前言
大家好我是醉墨居士今天聊一下计算机中的经典算法 - 二分算法
核心问题
查找升序数组中某个数的索引
遍历查找思路
我们直接从头到尾遍历数组查找
判断当前数是否是要查询的数
如果是则直接返回索引
如果当前数大于要查询的数直接返回-1
如果不是则继续向后查找
如果最终也没找到返回-1
遍历查找代码实现
def find_target(nums, target):for i in range(len(nums)):if nums[i] target:return iif nums[i] target:return -1return -1遍历查找缺点
遍历查找没有利用数组是升序的特点而是简单的暴力搜索无法进行有效的剪枝 时间复杂度O(N)空间复杂度O(1)
二分查找思路
二分查找的核心就是利用数组是有序的特点
每次取待查找的区间的中点
如果中点对应的数等于要查找的数直接返回中点索引
如果中点对应的数大于要查找的数则在待查找的区间的左半区域进行查找
如果中点对应的数小于要查找的数则在待查找的区间的右半区域进行查找
如果最终也没找到返回-1
二分查找代码实现
def binary_find(nums, target):low, high 0, len(nums) - 1while low high:mid (low high) 1if nums[mid] target:return midelif nums[mid] target:high mid - 1elif nums[mid] target:low mid 1 return -1二分查找优点
合理利用有序数组这个特点进行剪枝每次查找都会减少一半的查询范围 时间复杂度O(Log N)空间复杂度O(1)
二分查找的变种
问题一
查找大于等于某个数最左边的数的索引例如[0,1,2,2,3,6,7] 中查找2的索引是2
解题思路
每次取待查找的区间的中点
如果中点对应的数大于等于要查找的数则更新结果并在待查找的区间的左半区域进行查找
如果中点对应的数小于要查找的数则在待查找的区间的右半区域进行查找
如果最终也没找到返回结果
代码实现
def find_left(nums, target):low, high 0, len(nums) - 1ans -1while low high:mid (low high) 1if nums[mid] target:ans midhigh mid - 1else:low mid 1return ans问题二
查找旋转数组的最小值例如[4,5,6,7,0,1,2] 中的最小值为 0
解题思路
每次取待查找的区间的中点
如果中点对应的数大于右边界对应的数则在待查找的区间的右半区域进行查找
如果中点对应的数小于等于右边界对应的数则在待查找的区间的左半区域进行查找
直到最终查询完毕返回左端点对应的数
代码实现
def find_min(nums):low, high 0, len(nums) - 1while low high:mid (low high) 1 if nums[mid] nums[high]:low mid 1else:high midreturn nums[low]
