二分查找

xiufanivan · 2022-12-22 20:05:28 · 个人记录

题目：leetcode（704）704. 二分查找 - 力扣（LeetCode）

给定一个 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

代码：（左闭右闭，[low, high]，时刻考虑数据是否在范围内）

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int low = 0, high = nums.size() - 1;  // 注意这个size-1是数组最后一位

        while (low <= high)  // 若low = high = 1，[1, 1]合法，故是<=
        {
            int mid = low + (high - low) / 2;  // 防止超int范围，(low+high)/2可能会爆

            if (nums[mid] == target)
            {
                return mid;
            }
            else if (nums[mid] < target)
            {
                low = mid + 1;  // nums[mid]不是target，所以mid+1
            }
            else 
            {
                high = mid - 1;  // 同理
            }
        }
        return -1;
    }
};

代码：（左闭右开，[low, high)，时刻考虑数据是否在范围内）

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int low = 0, high = nums.size();  // 注意这个size是数组最后一位+1，右边开区间不包括在内

        while (low < high)  // 若low = high = 1，[1, 1)不合法，故是<
        {
            int mid = low + (high - low) / 2;  // 防止超int范围，(low+high)/2可能会爆

            if (nums[mid] == target)
            {
                return mid;
            }
            else if (nums[mid] < target)
            {
                low = mid + 1;  // nums[mid]不是target，所以mid+1
            }
            else 
            {
                high = mid;  // 右区间是开区间
            }
        }
        return -1;
    }
};

文章参考《代码随想录》二分查找：代码随想录 (二分查找)