题解 | #二分查找-I#

问题描述

想象一下，你有一排按大小顺序排列的卡片，每张卡片上有一个数字，而且每个数字都不一样。现在，你需要找到一张特定的卡片。如果找到了这张卡片，你就告诉别人这张卡片的位置；如果没有找到，你就说找不到。

示例

• 输入：[-1, 0, 3, 4, 6, 10, 13, 14], 13
• 输出：6
• 说明：13 出现在卡片中，位置是第 6 张卡片（从 0 开始数）。
• 输入：[], 3
• 输出：-1
• 说明：没有卡片，所以找不到。
• 输入：[-1, 0, 3, 4, 6, 10, 13, 14], 2
• 输出：-1
• 说明：2 这个数字不在卡片中，所以找不到。

解释

1. 准备阶段：
1. 把所有的卡片分成两堆：左边一堆和右边一堆。
2. 最开始，左边堆里包含第一张卡片，右边堆里包含最后一张卡片。
2. 查找过程：
1. 找出中间位置的卡片。
2. 如果中间位置的卡片上的数字正好是你想找的数字，那你就找到了！告诉别人它的位置。
3. 如果中间位置的卡片上的数字比你要找的数字小，那你就在右边堆里继续找。
4. 如果中间位置的卡片上的数字比你要找的数字大，那你就在左边堆里继续找。
5. 重复上面的步骤，直到找到或者确定找不到为止。
3. 结束：
1. 如果最后都没有找到，那就告诉别人找不到。

具体步骤

假设我们要找的数字是 13，卡片序列是 [-1, 0, 3, 4, 6, 10, 13, 14]：

1. 准备阶段：
1. 左边堆包含 -1，右边堆包含 14。
2. 查找过程：
1. 中间位置的卡片是 4（位置 3）。
2. 4 比 13 小，所以我们在右边堆继续找。
3. 右边堆现在包含 [6, 10, 13, 14]。
4. 新的中间位置的卡片是 13（位置 6）。
5. 13 正是我们要找的数字！
3. 结束：
1. 我们找到了 13，位置是 6。

Java 实现

下面是具体的 Java 代码实现：

public class BinarySearch {

    // 二分查找
    public static int search(int[] nums, int target) {
        int left = 0; // 左边堆的起始位置
        int right = nums.length - 1; // 右边堆的结束位置

        while (left <= right) { // 只要左边堆的起始位置不大于右边堆的结束位置
            int mid = left + (right - left) / 2; // 计算中间位置

            if (nums[mid] == target) {
                return mid; // 找到了，返回位置
            } else if (nums[mid] < target) {
                left = mid + 1; // 在右边堆继续找
            } else {
                right = mid - 1; // 在左边堆继续找
            }
        }

        return -1; // 没找到
    }

}

示例1

输入：[-1, 0, 3, 4, 6, 10, 13, 14], 13

• 输出：找到了 13，位置是 6。

示例2

输入：[], 3

• 输出：没有找到 3。

示例3

输入：[-1, 0, 3, 4, 6, 10, 13, 14], 2

• 输出：没有找到 2。

如果这篇文章对你有帮助，请点个免费的赞👍，让它能够帮助更多人。