704.二分查找

LeetCode LeetCode 数组二分查找

发布时间 : 2000-01-10 07:00

字数:1.5k 阅读 :

评论:

704.二分查找

704.二分查找

704.1 题目

给定一个 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] 之间。

704.2 题解

方法一：遍历数组查找

思路

遍历数组中的每个元素，逐一与目标值比较。找到目标值则返回当前索引，遍历结束仍未找到则返回 -1。简单直接，但未利用数组有序的特性。

核心思想：线性遍历，逐一比较。

具体步骤：

遍历数组每个元素。
如果找到目标值，返回当前索引。
遍历结束仍未找到，返回 -1。

举例：对于 nums = [-1,0,3,5,9,12], target = 9：

i=0：-1 != 9
i=1：0 != 9
i=2：3 != 9
i=3：5 != 9
i=4：9 == 9，返回 4

复杂度分析

时间复杂度：O(n)，最坏情况需要遍历整个数组。
空间复杂度：O(1)，只使用常数额外空间。

代码

// 方法一：遍历数组查找
static int Search1(int[] nums, int target)
{
    for (int i = 0; i < nums.Length; i++)
    {
        if (nums[i] == target)
        {
            return i;
        }
    }

    return -1;
}

方法二：二分查找

思路

利用数组有序的特性，每次将搜索范围缩小一半。初始化左右指针分别指向数组首尾。比较中间元素与目标值：若相等则返回索引；若中间元素较大，则在左半边继续查找；否则在右半边查找。循环终止条件为左指针超过右指针。

核心思想：每次将搜索范围缩小一半。

具体步骤：

初始化 left = 0, right = n - 1。
当 left <= right 时：
- 计算 mid = (left + right) / 2
- 如果 nums[mid] == target：返回 mid
- 如果 nums[mid] > target：right = mid - 1
- 如果 nums[mid] < target：left = mid + 1
返回 -1。

举例：对于 nums = [-1,0,3,5,9,12], target = 9：

left=0, right=5：mid=2，nums[2]=3 < 9，left=3
left=3, right=5：mid=4，nums[4]=9 == 9，返回 4

复杂度分析

时间复杂度：O(log n)，每次迭代将搜索范围减半。
空间复杂度：O(1)，只使用常数额外空间。

代码

// 方法二：二分查找
static int Search2(int[] nums, int target)
{
    // 初始化左右指针，表示搜索范围的起始和结束位置
    int left = 0;
    int right = nums.Length - 1;

    // 使用二分查找进行搜索
    while (left <= right)
    {
        // 计算中间位置的索引
        int mid = (left + right) / 2;

        // 如果中间元素大于目标值，说明目标值可能在左半边
        if (nums[mid] > target)
        {
            // 更新右指针，缩小搜索范围为左半边
            right = mid - 1;
        }
        // 如果中间元素小于目标值，说明目标值可能在右半边
        else if (nums[mid] < target)
        {
            // 更新左指针，缩小搜索范围为右半边
            left = mid + 1;
        }
        // 如果中间元素等于目标值，表示找到目标值，返回索引
        else
        {
            return mid;
        }
    }

    // 如果循环结束仍未找到目标值，返回 -1 表示目标值不存在
    return -1;
}

704.3 代码

using System;

class Program
{
    static void Main()
    {
        #region 题目

        // 给定一个 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]之间。

        #endregion

        #region 测试

        // 示例 1
        int[] nums1 = { -1, 0, 3, 5, 9, 12 };
        int target1 = 9;
        int result1 = Search1(nums1, target1);
        Console.WriteLine($"示例1 方法1 输出：{result1}");
        int result1_2 = Search2(nums1, target1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        int[] nums2 = { -1, 0, 3, 5, 9, 12 };
        int target2 = 2;
        int result2 = Search1(nums2, target2);
        Console.WriteLine($"示例2 方法1 输出：{result2}");
        int result2_2 = Search2(nums2, target2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        #endregion
    }

    #region 答案

    // 方法一：遍历数组查找
    static int Search1(int[] nums, int target)
    {
        for (int i = 0; i < nums.Length; i++)
        {
            if (nums[i] == target)
            {
                return i;
            }
        }

        return -1;
    }

    // 方法二：二分查找
    static int Search2(int[] nums, int target)
    {
        // 初始化左右指针，表示搜索范围的起始和结束位置
        int left = 0;
        int right = nums.Length - 1;

        // 使用二分查找进行搜索
        while (left <= right)
        {
            // 计算中间位置的索引
            int mid = (left + right) / 2;

            // 如果中间元素大于目标值，说明目标值可能在左半边
            if (nums[mid] > target)
            {
                // 更新右指针，缩小搜索范围为左半边
                right = mid - 1;
            }
            // 如果中间元素小于目标值，说明目标值可能在右半边
            else if (nums[mid] < target)
            {
                // 更新左指针，缩小搜索范围为右半边
                left = mid + 1;
            }
            // 如果中间元素等于目标值，表示找到目标值，返回索引
            else
            {
                return mid;
            }
        }

        // 如果循环结束仍未找到目标值，返回 -1 表示目标值不存在
        return -1;
    }

    #endregion
}

704.4 运行结果

示例1 方法1 输出：4
示例1 方法2 输出：4
示例2 方法1 输出：-1
示例2 方法2 输出：-1

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com