题解 | #二分查找-I#

题目描述:请实现无重复数字的升序数组的二分查找，给定一个 元素升序的、无重复数字的整型数组 和一个目标值 ，写一个函数搜索 中的 ，如果目标值存在返回下标（下标从 0 开始），否则返回 -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 不存在nums中因此返回 -1
思路：二分查找适用于已排序数组，算法执行的时间复杂度为O(logn)，两个指针low和high，通过low和high找mid，判断mid和目标值的大小关系来更新low或high即可。具体代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int search(vector<int>& nums, int target) {
        // write code here
        int res = -1;
        int n = nums.size();
        if(n == 0) return -1;
        else
        {
            if(target<nums[0] || target>nums[n-1])
                return -1;
            else
            {
                int low = 0,high= n-1,mid;
                while(low<=high)
                {
                    mid = low +(high-low)/2;
                    if(nums[mid] == target)
                    {
                        res = mid;
                        break;
                    }
                    else
                    {
                        if(nums[mid] > target)
                        {
                            high = mid-1;
                        }
                        else
                        {
                            low = mid+1;
                        }
                    }
                }
                return res;
            }
        }
    }
};