二分查找

二分查找是在有序数组中进行查询的方法，思路虽简单，但是关于各种边界、+1、-1，总是会出现错误。这里以左闭右闭的形式，进行总结，做到简单易懂。

1. 普通二分查找
   high选取的是len(nums)-1，如此形成的是左闭右闭区间，也有很多其他地方使用左闭右开，但我觉得不易于理解和记忆。
   mid我们使用low + (high-low)/2来获取，是为了避免溢出，(high+low)/2分子可能会超出数据上限。
   因为左闭右闭，所以mid位置的数据我们已经查询过，所以小于target，我们将low=mid+1。大于target，high=mid-1。等于直接返回。没有查找到返回-1。另外循环条件是<=，也需要注意下。

   func search(nums []int, target int) int {
   	low := 0
   	high := len(nums) - 1
   	for low <= high {
   		mid := low + (high-low)/2
   		if nums[mid] < target {
   			low = mid + 1
   		} else if nums[mid] > target {
   			high = mid - 1
   		} else if nums[mid] == target {
   			return mid
   		}
   	}
   	return -1
   }

2. 左边界查找
   主体上和普通二分查找差别不大，但要注意三个差异点。
   一是相等时high = mid - 1，因为我们是查找左边界，当相等的时候，可能左侧还有符合的数字，此时需要收缩右边界。
   二是返回值为low，我们记住查做边界，那么返回左侧。结合上一条思考下，为什么这样可以返回符合的值呢？当nums[mid]==target，收缩边界，假若此时mid正好是左边界位置，那么对[low,mid-1]继续查询，因为一直小于low不断+1，知道low>mid-1，即mid。
   三是特殊判断，因为low的取值是不停+1，最坏情况超出上界，需要做处理，另外当循环中断时，返回索引可能不符合条件，同样要判断。

   func left(nums []int, target int) int {
   	low := 0
   	high := len(nums) - 1
   	for low <= high {
   		mid := low + (high-low)/2
   		if nums[mid] < target {
   			low = mid + 1
   		} else if nums[mid] > target {
   			high = mid - 1
   		} else if nums[mid] == target {
   			high = mid - 1 //注意
   		}
   	}
   	if low >= len(nums) || nums[low] != target { //注意
   		return -1
   	}
   	return low //注意
   }

3. 右边界查找
   基本和查做边界差不多，差异在：
   low=mid+1收缩左边界
   high不停-1，做边界检查
   查询的是右边界，返回值为high

   func right(nums []int, target int) int {
   	low := 0
   	high := len(nums) - 1
   	for low <= high {
   		mid := low + (high-low)/2
   		if nums[mid] < target {
   			low = mid + 1
   		} else if nums[mid] > target {
   			high = mid - 1
   		} else if nums[mid] == target {
   			low = mid + 1 //注意
   		}
   	}
   	if high < 0 || nums[high] != target { //注意
   		return -1
   	}
   	return high //注意
   }