leetcode之704 二分查找

每日碎碎念

苦痛生活今日起
从今天开始LeetCode打卡，一边重新刷题，一边春招等笔面试，人生苦痛…

一、题目要求及测试点

704 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
链接https://leetcode.cn/problems/binary-search/submissions/520897723

测试点

示例 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]之间。 nums 的每个元素都将在 [-9999,9999]之间。

二、题解

自己上手

代码如下：

class Solution {
public:
    int search(vector<int>& nums, int target) { 
        int i = 0; 
        for (i = 0; i < nums.size(); i++){ 
            if (nums[i] == target)
                return i; 
        }
        if (i == nums.size())
            return -1; 
        else
            return 0; 
    }
};

来点无用总结：
时间复杂度O（n），return 的情况要设置完全，vector容器用nums.size()获取长度，注意写代码规范…

正经题解

提示中已说明该数列有序，且无重复，考虑二分

二分法之左闭右闭

class Solution {
public:
    int search(vector<int>& nums, int target) { 
        int left = 0; 
        int right = nums.size() - 1; 
        while (left <= right){ 
            int middle = left + ((right - left) / 2);
            if (nums[middle] < target)
                left = middle + 1; 
            else if(nums[middle] > target)
                right = middle - 1; 
            else
                return middle; 
        }
        return -1; 
    }
};

时间复杂度：O(log n),空间复杂度：O(1)

二分法之左闭右开

class Solution {
public:
    int search(vector<int>& nums, int target) { 
        int left = 0; 
        int right = nums.size(); 
        while (left < right){ 
            int middle = left + ((right - left) >> 1);
            if (nums[middle] < target)
                left = middle + 1; 
            else if(nums[middle] > target)
                right = middle; 
            else
                return middle; 
        }
        return -1; 
    }
};

三、总结

1.注意二分法使用前提；
2.左闭右闭时，长度-1，left≤right，左区间替换时middle-1;左闭右开时，长度不变，left＜right，左区间替换时middle;
3.nums.size(),编程规范注意一下