在做题中学习（48）：朴素的二分查找

. - 力扣（LeetCode）

解法一： 暴力求解

for循环中，从nums[0]枚举到nums[n-1]，依次判断，返回 == target的值。

时间复杂度 : O(N)    :因为要遍历一遍数组

解法二：二分查找

因为此数组为有序的数组，所以可以每次取数组中心元素来比较，<target就往右移动，>target就往左移动，之后由新的left right更新mid，若mid所在位置的值 == target 则返回mid 下标

1.mid < target  left++

2.mid > target right--

3.mid == target return mid;

时间复杂度：O(logN)

细节问题：

1. 求中间元素

(left + right) /2    这种求法又可能会溢出（如果left + right足够大的话），因此建议用下面的求法：

left + (right - left) /2     又可能会见到 left + (right - left + 1) /2 

两种的区别是：当元素数量为偶数时，会指向不同的值。

class Solution {
public:
    int search(vector<int>& nums, int target) 
    {
        int left = 0,right = nums.size()-1;
        while(left<=right)
        {
            int mid = left + (right - left) /2;
            if(nums[mid] < target)
                left = mid + 1;
            else if(nums[mid] > target)
                right = mid - 1;
            else 
                return mid;
        }
        return -1;
    }
};