题解 | #二分查找-I#

秒懂【反转链表】！超清晰图解一步步拆解。

1.思路

先来看一下什么是二分查找？

二分查找是一种高效的搜索算法，适用于有序数组。其核心思想是通过不断缩小搜索范围，将时间复杂度降至 O(log n)。

核心步骤：

1. 初始化指针：设置左指针 left = 0，右指针 right = 数组长度 - 1。

2. 循环查找：当 left <= right 时，重复以下步骤： 计算中间索引 mid = left + (right - left) // 2（避免整数溢出）。 比较中间元素 arr[mid] 与目标值 target： 若相等，返回 mid。 若 arr[mid] < target，说明目标在右侧，更新 left = mid + 1。 若 arr[mid] > target，说明目标在左侧，更新 right = mid - 1。

3. 未找到：若循环结束未找到，返回 -1。

假如要查找的有序数组、查找元素如下图所示：

定义两个变量left、right，分别指向数组的第0个位置和最后一个位置。这两个变量组成的区间为：[0,n-1]。通过循环缩小数组区间，查找对应的元素，具体操作如下：

关键点

1. 初始区间：通常使用左闭右闭区间 [left, right]，即 left = 0，right = len(nums) - 1。
2. 循环条件：while left <= right，确保所有元素被检查。
3. 中间位置计算：mid = (left + right) // 2 或 mid = left + (right - left) // 2（避免溢出）。
4. 边界更新：
   • 找到目标时，标准二分查找直接返回。
   • 寻找左边界时，中间元素 Arr[mid]>= target 则移动右边界。
   • 寻找右边界时，中间元素 Arr[mid] <= target 则移动左边界。

如果文字描述的不太清楚，你可以参考视频的详细讲解：B站@好易学数据结构

2.代码

2.1 Python代码

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # write code here
        # 1.定义变量
        left = 0
        right = len(nums) - 1
        # 2.通过循环缩小查询区间
        while left <= right:
            # 2.1 计算中间位置（数组下标）
            mid = (left + right) // 2
            # 2.2 与目标值比较，缩小区间
            if nums[mid] == target:
                return mid  # 中间位置对应的值 等于 目标值，找到，直接返回
            elif nums[mid] < target:
                left = mid + 1  # 中间位置对应的值 小于 目标值，则到右侧区间查找（缩小区间：[mid+1,n]）
            else:
                right = mid - 1  # 中间位置对应的值 大于 目标值，则到左侧区间查找（缩小区间：[0,mid-1]）

   return -1  # 未找到，返回-1

2.2 Java代码

public static class Solution {
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * @param nums   int整型一维数组
         * @param target int整型
         * @return int整型
         */
        public int search(int[] nums, int target) {
            // write code here
            // 1. 定义变量
            int left = 0;
            int right = nums.length - 1;
            // 2. 通过循环缩小查询区间
            while (left <= right) {
                // 2.1 计算中间位置（数组下标）
                int mid = (left + right) / 2;
                // 2.2 与目标值比较，缩小区间
                if (nums[mid] == target) {
                    return mid; //中间位置对应的值 等于 目标值，找到，直接返回
                } else if (nums[mid] < target) {
                    left = mid + 1; //中间位置对应的值 小于 目标值，则到右侧区间查找（缩小区间：[mid+1,n]）
                } else {
                    right = mid - 1;  //中间位置对应的值 大于 目标值，则到左侧区间查找（缩小区间：[0,mid-1]）
                }
            }
            return -1; //未找到，返回-1
        }
    }

  

2.3 Go代码

func search(nums []int, target int) int {
	// write code here
	// 1. 定义变量
	left := 0
	right := len(nums) - 1
	// 2. 通过循环缩小查询区间
	for left <= right {
		// 2.1 计算中间位置（数组下标）
		mid := (left + right) / 2
		// 2.2 与目标值比较，缩小区间
		if nums[mid] == target {
			return mid //中间位置对应的值 等于 目标值，找到，直接返回
		} else if nums[mid] < target {
			left = mid + 1 //中间位置对应的值 小于 目标值，则到右侧区间查找（缩小区间：[mid+1,n]）
		} else {
			right = mid - 1 //中间位置对应的值 大于 目标值，则到左侧区间查找（缩小区间：[0,mid-1]）
		}
	}
	return -1
}

如果上面的代码理解的不是很清楚，你可以参考视频的详细讲解：B站@好易学数据结构