尧图网页设计 
一、数据结构基本介绍什么是数据结构数据结构是计算机中组织、存储和管理数据的一套方式。现实世界里我们会把物品分类存放方便查找、取用在程序当中数据同样需要合理的组织方式这就是数据结构。程序处理的本质就是对数据做操作存储、查询、插入、删除、修改。不同的数据结构在完成同样操作时消耗的时间和内存是不一样的。学习数据结构核心目的就是根据业务场景选择合适的数据结构优化程序的执行效率。数据结构的分类数据结构可以分为两大类别线性结构与非线性结构。1. 线性结构数据元素之间是一对一的关系排成一条直线。常见数组、链表、栈、队列。数组连续内存支持下标随机访问链表离散内存依靠指针串联栈后进先出LIFO队列先进先出FIFO。2. 非线性结构元素之间是一对多、多对多的关系。常见树、图、哈希表。树一对多例如二叉树图多对多用来表示网络关系。算法与数据结构的关系数据结构是数据存放的容器算法是处理数据的方法二者相辅相成。举个例子在有序数组中查找目标值。如果使用暴力遍历从头到尾逐个对比时间复杂度 O(n)如果使用二分查找算法每次直接排除一半数据时间复杂度优化到 O(\log n)。数据结构提供存储载体算法负责高效操作数据。学习顺序先掌握基础线性结构数组、链表再学习栈、队列之后再学习树、图等复杂结构。二、数组基本概念数组的定义数组是一种连续的、固定大小的线性数据结构在内存中开辟一块连续的存储空间存放一组相同类型的数据。数组核心特性1. 内存连续数组的所有元素在内存地址上是紧挨着的没有空隙。这是数组最重要的特点。正因为内存连续数组可以通过下标直接定位元素实现随机访问访问任意下标元素的时间复杂度为 O(1)。2. 下标从0开始绝大多数编程语言C/C、Python、Java数组下标起始为0。数组第一个元素下标为0第二个下标为1以此类推。对于长度为n的数组合法下标范围是 0 \sim n-1。注意下标不能越界如果访问下标等于数组长度就会发生数组越界错误。3. 长度固定静态数组一旦创建数组的总长度就不能改变。如果想要存放更多元素只能重新开辟一块更大的内存空间把旧数组的数据复制过去。Python中的list虽然可以动态append底层本质也是数组扩容机制。数组与二分查找的关系二分查找能够生效前提条件是数组必须有序。数组拥有随机访问能力我们可以快速拿到中间位置的元素不断缩小查找区间。如果是无序数组无法使用二分查找只能暴力遍历。LeetCode704题目给出的就是升序数组正好适合二分查找。三、二分查找两种区间写法解题思路本题为有序数组的目标值查找利用二分查找可以将时间复杂度优化至 O(log n)。根据区间定义不同分为左闭右闭和左闭右开两种标准写法核心逻辑为不断缩小查找区间直至找到目标或区间为空。一、写法一左闭右闭区间 [left, right]1. 区间定义查找区间为 左右边界均包含 的有效下标区间。初始化左指针 left 0 右指针 right len(nums) - 1 区间内所有下标都是合法查找范围。2. 循环条件循环条件设置 right 。 原因当 left right 时区间内仍保留一个有效元素需要进入循环判断只有 left right 时区间彻底为空查找结束。3. 区间收缩逻辑每次取中间位置 mid left (right - left) // 2 避免数值溢出1. 若 nums[ target 目标值在右侧区间mid 位置已排除更新左边界 left mid 12. 若 nums[mid] target 目标值在左侧区间mid 位置已排除更新右边界 right mid - 13. 若 nums[mid] target 找到目标元素直接返回当前下标 mid4. 结果处理循环正常退出说明区间内无目标值返回 -1。复杂度时间复杂度O(log n)每次查找区间长度减半空间复杂度O(1)仅使用常数变量二、写法二左闭右开区间 [left, right)1. 区间定义查找区间为 包含左边界、不包含右边界。初始化左指针 left 0 右指针 right len(nums) right 为数组边界外下标不属于查找区间。2. 循环条件循环条件设置为 while left right 。原因左、右指针相等时区间 [left, right) 为空无元素可判断直接结束循环。3. 区间收缩逻辑同样取中间位置 mid left (right - left) // 2 1. 若 nums[mid] target 目标在右侧更新左边界 left mid 12. 若 nums[mid] target 目标在左侧因右边界为开区间mid 本身不在区间内直接更新右边界 right mid3. 若 nums[mid] target 找到目标元素返回下标 mid4. 结果处理循环结束未匹配到目标值返回 -1。复杂度时间复杂度O(log n)空间复杂度O(1)总结两种写法核心区别由区间定义决定三者必须统一1. 左闭右闭 rightlen-right 、 rightmid-12. 左闭右开 rightlen right 、 rightmid两种算法效率完全一致仅边界处理逻辑不同。 数据结构入门：数组与二分查找（LeetCode704）
一、数据结构基本介绍什么是数据结构数据结构是计算机中组织、存储和管理数据的一套方式。现实世界里我们会把物品分类存放方便查找、取用在程序当中数据同样需要合理的组织方式这就是数据结构。程序处理的本质就是对数据做操作存储、查询、插入、删除、修改。不同的数据结构在完成同样操作时消耗的时间和内存是不一样的。学习数据结构核心目的就是根据业务场景选择合适的数据结构优化程序的执行效率。数据结构的分类数据结构可以分为两大类别线性结构与非线性结构。1. 线性结构数据元素之间是一对一的关系排成一条直线。常见数组、链表、栈、队列。数组连续内存支持下标随机访问链表离散内存依靠指针串联栈后进先出LIFO队列先进先出FIFO。2. 非线性结构元素之间是一对多、多对多的关系。常见树、图、哈希表。树一对多例如二叉树图多对多用来表示网络关系。算法与数据结构的关系数据结构是数据存放的容器算法是处理数据的方法二者相辅相成。举个例子在有序数组中查找目标值。如果使用暴力遍历从头到尾逐个对比时间复杂度 O(n)如果使用二分查找算法每次直接排除一半数据时间复杂度优化到 O(\log n)。数据结构提供存储载体算法负责高效操作数据。学习顺序先掌握基础线性结构数组、链表再学习栈、队列之后再学习树、图等复杂结构。二、数组基本概念数组的定义数组是一种连续的、固定大小的线性数据结构在内存中开辟一块连续的存储空间存放一组相同类型的数据。数组核心特性1. 内存连续数组的所有元素在内存地址上是紧挨着的没有空隙。这是数组最重要的特点。正因为内存连续数组可以通过下标直接定位元素实现随机访问访问任意下标元素的时间复杂度为 O(1)。2. 下标从0开始绝大多数编程语言C/C、Python、Java数组下标起始为0。数组第一个元素下标为0第二个下标为1以此类推。对于长度为n的数组合法下标范围是 0 \sim n-1。注意下标不能越界如果访问下标等于数组长度就会发生数组越界错误。3. 长度固定静态数组一旦创建数组的总长度就不能改变。如果想要存放更多元素只能重新开辟一块更大的内存空间把旧数组的数据复制过去。Python中的list虽然可以动态append底层本质也是数组扩容机制。数组与二分查找的关系二分查找能够生效前提条件是数组必须有序。数组拥有随机访问能力我们可以快速拿到中间位置的元素不断缩小查找区间。如果是无序数组无法使用二分查找只能暴力遍历。LeetCode704题目给出的就是升序数组正好适合二分查找。三、二分查找两种区间写法解题思路本题为有序数组的目标值查找利用二分查找可以将时间复杂度优化至 O(log n)。根据区间定义不同分为左闭右闭和左闭右开两种标准写法核心逻辑为不断缩小查找区间直至找到目标或区间为空。一、写法一左闭右闭区间 [left, right]1. 区间定义查找区间为 左右边界均包含 的有效下标区间。初始化左指针 left 0 右指针 right len(nums) - 1 区间内所有下标都是合法查找范围。2. 循环条件循环条件设置 right 。 原因当 left right 时区间内仍保留一个有效元素需要进入循环判断只有 left right 时区间彻底为空查找结束。3. 区间收缩逻辑每次取中间位置 mid left (right - left) // 2 避免数值溢出1. 若 nums[ target 目标值在右侧区间mid 位置已排除更新左边界 left mid 12. 若 nums[mid] target 目标值在左侧区间mid 位置已排除更新右边界 right mid - 13. 若 nums[mid] target 找到目标元素直接返回当前下标 mid4. 结果处理循环正常退出说明区间内无目标值返回 -1。复杂度时间复杂度O(log n)每次查找区间长度减半空间复杂度O(1)仅使用常数变量二、写法二左闭右开区间 [left, right)1. 区间定义查找区间为 包含左边界、不包含右边界。初始化左指针 left 0 右指针 right len(nums) right 为数组边界外下标不属于查找区间。2. 循环条件循环条件设置为 while left right 。原因左、右指针相等时区间 [left, right) 为空无元素可判断直接结束循环。3. 区间收缩逻辑同样取中间位置 mid left (right - left) // 2 1. 若 nums[mid] target 目标在右侧更新左边界 left mid 12. 若 nums[mid] target 目标在左侧因右边界为开区间mid 本身不在区间内直接更新右边界 right mid3. 若 nums[mid] target 找到目标元素返回下标 mid4. 结果处理循环结束未匹配到目标值返回 -1。复杂度时间复杂度O(log n)空间复杂度O(1)总结两种写法核心区别由区间定义决定三者必须统一1. 左闭右闭 rightlen-right 、 rightmid-12. 左闭右开 rightlen right 、 rightmid两种算法效率完全一致仅边界处理逻辑不同。