题解 | #二分查找-I#

二分查找-I

http://www.nowcoder.com/practice/d3df40bd23594118b57554129cadf47b

二分查找

问题描述：请实现无重复数字的升序数组的二分查找。给定一个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1

示例1

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

返回值：6

说明：13 出现在nums中并且下标为 6

示例2

输入：[],3

返回值：-1

说明：nums为空，返回-1

示例3

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

返回值：-1

说明：2不在数组中

方法一

思路分析

本题目思路很清楚，如果不使用二分查找，由于数组是升序，直接从左到右顺序查找，如果找到直接返回所在位置，如果没有返回-1。

C++核心代码

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();
        if(n==0) return -1;
        for(int i=0;i<n;i++)
        {
            if(nums[i]==target)//按顺序查找
                return i;
        }
        return -1;//没有找到返回-1
    }
};

复杂度分析

时间复杂度：一层循环遍历，因此时间复杂度为$O(n)$
空间复杂度: 空间复杂度为$O(1)$

方法二

思路分析

本题是想要考察二分查找的思想。二分查找法作为一种常见的查找方法，将原本是线性时间提升到了对数时间范围，大大缩短了搜索时间，但它有一个前提，就是必须在有序数据中进行查找，而本题给的数组是升序的。一个升序数组，比较一个元素与数组中的中间位置的元素的大小，如果比中间位置的元素大，则继续在后半部分的数列中进行二分查找；如果比中间位置的元素小，则在数组的前半部分进行比较；如果相等，则找到了元素的位置。每次比较的数组长度都会是之前数组的一半，直到找到相等元素的位置或者最终没有找到要找的元素。

图解

C++核心代码

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();
        if(n==0) return -1;
        int left=0,right=n-1;
        int mid;
        while(left<=right)
        {
            mid=left+(right-left)/2; //中间位置元素
            if(nums[mid]==target)
                return mid;
            else if(nums[mid]>target)//中间位置元素大于目标值，因此目标值如果在数组中，必在中间位置左侧
                right=mid-1;//设置右侧标志为中间位置-1
            else  //中间位置元素小于目标值，因此目标值如果在数组中，必在中间位置右侧
                left=mid+1;//设置左侧标志为中间位置+1
        }
        return -1;//没有找到返回-1
    }
};