刷题第1天：leetcode704--数组元素查找--二分法查找算法

第一部分---数组的基础知识介绍：

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

提示：

1. 你可以假设 nums 中的所有元素是不重复的。
2. n 将在 [1, 10000]之间。
3. nums 的每个元素都将在 [-9999, 9999]之间。

题目分析：本题的关键词为：有序数组；数组中无重复元素。这两者是使用二分法的前提条件。当然使用暴力解法进行遍历判别很容易做出来本题，但是计算复杂度比较高，所以不推荐。我们在此使用二分法，并采用左闭右闭的原则进行python代码编写。代码中共有3个需要更新的变量：left，right，middle。

#二分法，左闭右闭原则.注意本代码需要在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的值计算更新middle

            if 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)

总结：根据二分法适用的两个前提条件（有序数组，无重复元素）识别使用该方法的场景，使用左闭右闭原则书写代码。

原文地址：https://blog.csdn.net/qq_43449643/article/details/136308115

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！