LeetCode 704.二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

非常简单易懂的题目，要求就是返回相应元素的下标。但这题的重点在于时间复杂度要实现O(log n)，如果您以后一看到要求这样的时间复杂度，那么就应该下意识地反应到这可能是一道需求二分算法求解的题目。如果没有这样的要求，我们完全可以使用时间复杂度为O(n)的遍历数组。

因为比较简单，所以就不详细展开了，您如果不理解二分法可以根据下面代码的注释来辅助理解。

代码示例

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int min=0,max=nums.size()-1,mid=0;
        while(min<=max)//在min>max后退出循环，则代表target在nums中不存在
        {
            mid=(int)(min+max)/2;//获取数组的中间下标
            if(nums[mid]<target)  //如果nums[mid]小于需要查找的target，则将范围缩小到mid+1与max之间
                min=mid+1; 
            else if(nums[mid]>target)  //反之如果大于target，则将范围缩小到min与mid-1之间
                max=mid-1;
            else  //如果是相等就直接返回下标即可
                return mid;
        }
        return -1;
    }
};