NC160 题解 | #二分查找-I#

题意分析

• 在一个升序，没有重复元素的序列里面找到一个固定的目标值，返回这个下标，没有就返回-1

思路分析

解法一 循环遍历

• 直接对整个数组进行暴力求解，遍历整个数组即可。
• 代码如下
  • 遍历的时间复杂度为$O(n)O(n)$
  • 过程中只用了少数几个变量，空间复杂度为$O(1)O(1)$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int search(vector<int>& nums, int target) {
        // write code here
        int n = nums.size();
        // 直接遍历整个数组
        for(int i=0;i<n;i++){
            if(nums[i]==target){
                return i;
            }
        }
        // 特判的情况
        return -1;
    }
};

解法二 二分求解

• 这个就是一个典型的二分的题目，由于整个序列具有单调性，所以我们可以二分最后的这个数字的位置。每次二分有三种情况
  • nums[mid]<target,l=mid+1,
  • nums[mid]>target,r=mid-1
  • nums[mid]=target, 直接返回mid即可

• 代码如下
  • 每次将区间缩小一半，总的时间复杂度为$O(logn)O(logn)$
  • 过程中只需要几个变量，空间复杂度为$O(1)O(1)$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int search(vector<int>& nums, int target) {
        // write code here
        int l=0,r=nums.size(),mid;
        // 特判为空的情况
        if(l==r){
            return -1;
        }
        // 二分区间左右端点
        while(l<=r){
            mid=(l+r)>>1;
            if(nums[mid]>target){
                r=mid-1;
            }else if(nums[mid]<target){
                l=mid+1;
            }else{
                return mid;
            }
        }
        return -1;
    }
};