哪些网站容易被百度收录,做分类网站用什么cms,兰州网站优化哪家好,网站开发行业标准第一部分---数组的基础知识介绍#xff1a;
1.数组的定义#xff1a;数组是存放在连续内存空间上的相同数据类型的数据的集合#xff1b;
2.数组可以通过下标索引的方式获取到下标对应的数据#xff1b;
3.数组下标是从0开始的#xff0c;数组的内存空间地址是连续的
1.数组的定义数组是存放在连续内存空间上的相同数据类型的数据的集合
2.数组可以通过下标索引的方式获取到下标对应的数据
3.数组下标是从0开始的数组的内存空间地址是连续的正因为地址是连续的所以在对数组进行删除或者增添相应元素的时候难免需要移动其它数组元素的位置
4.数组的元素是不能删的只能覆盖。 第二部分--二分查找法介绍
leetcode 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提示
你可以假设 nums 中的所有元素是不重复的。n 将在 [1, 10000]之间。nums 的每个元素都将在 [-9999, 9999]之间。 题目分析本题的关键词为有序数组数组中无重复元素。这两者是使用二分法的前提条件。当然使用暴力解法进行遍历判别很容易做出来本题但是计算复杂度比较高所以不推荐。我们在此使用二分法并采用左闭右闭的原则进行python代码编写。代码中共有3个需要更新的变量leftrightmiddle。
#二分法左闭右闭原则.注意本代码需要在leetcode刷题环境下运行
class Sultion:def search(self, nums:List[int], target:int) - int:left, right 0, len(nums)-1 # 定义target在左闭右闭的区间里[left, right]while left right:middle left (right -left) // 2 # 根据left和right的值计算更新middleif nums[middle] target:right middle -1 # target在左区间所以[left, middle - 1]elif nums[middle] target:left middle 1 # target在右区间所以[middle 1, right]else:return middle # 数组中找到目标值直接返回下标return -1 # 未找到目标值时间复杂度Olog(n)
空间复杂度O(1)
总结根据二分法适用的两个前提条件有序数组无重复元素识别使用该方法的场景使用左闭右闭原则书写代码。
