【数组】二分查找

二分算法较为简单，但是其中有几点需要注意：

• 数组必须为有序数组，且数组中必须无重复元素（如果有重复元素，则返回下标可能不唯一）
• 在我们这种写法中，我们定义target是在一个闭区间[left,right]中，注意：
  • while(left≤right)，因为left==right时我们仍要查找这个位置序号上的元素
  • 如果nums[middle]>target，将right设为middle-1；若nums[middle]<target，将left设为middle+1

int search(int* nums, int numsSize, int target){
    int left = 0;
    int right = numsSize-1;
    int middle = 0;
		//若left小于等于right，说明区间中元素不为0
    while(left<=right) {
				//更新查找下标middle的值
        middle = (left+right)/2;
				//此时target可能会在[left,middle-1]区间中
        if(nums[middle] > target) {
            right = middle-1;
        } 
				//此时target可能会在[middle+1,right]区间中
        else if(nums[middle] < target) {
            left = middle+1;
        } 
				//当前下标元素等于target值时，返回middle
        else if(nums[middle] == target){
            return middle;
        }
    }
		//若未找到target元素，返回-1
    return -1;
}