[数据结构与算法]leetcode数组部分：704. 二分查找

704. 二分查找

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

示例 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

提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

思路：

超出时间限制：对核心的循环部分做了剪枝，i,j不能以m为两端，会增加循环次数，设置：i=m+1,j=m-1
执行出错：对i，j的边界限制没有明确，i不能超出vector长度，j不能为负；对于j的初始值设置没有考虑到数组长度为1时，会超出数组长度。

代码：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int i,j,m;
        i=0;
        j=nums.size()-1;
        printf("%d,%d\n",i,j);
        if(i==j){
            if(nums[i]==target)
                return 0;
        }
        //数组长度大于1
        while(i!=j){
            m=i+(j-i)/2;    //取中间值
            printf("%d,%d\n",i,j);
            printf("%d\n",m);
            if(nums[m]==target)
                return m;
            if(nums[i]==target)
                return i;
            if(nums[j]==target)
                return j;
            else if(nums[m]<target)//目标应在右侧
                if(m+1<nums.size())
                    i=m+1;
                else
                    i=m;
            else{
                if(m-1>=0)
                    j=m-1;
                else 
                    j=m;
            }
        }
        return -1;
    }
};