题目：704. 二分查找
思路：
二分查找一般是在有序的数组中查找指定的值，单纯的查找值，把数组跑一遍的复杂度为O(n)。
二分查找每次把范围缩小一半，我们每次都去中间的值，有以下三种情况：
- 如果mid位置的值比target大，那么target应该在mid左侧的位置(由小到大排序情况下)
- 如果mid位置的值比target小，那么target应该在mid右侧的位置(由小到大排序情况下)
- 如果mid位置的值等于target，返回mid
分治的思想不断重复上述过程(for循环)直到left和right达到某种状态停止，此时如果没有返回，说明数组内没有目标值，二分的时间复杂度为O(log2N)
二分查找法一般又分为两种：左闭右闭以及左闭右开，即[left,right]以及[left,right)。
- 当在[left,right]中查找目标值时，
left=right是有意义的(理解为[1,1]是有意义的)，因此不能忽略掉。- 结束条件为
for left <= right； - 当
x[mid] < target时，mid所在位置不是目标值，left又是闭区间本身是具有意义，因此left = mid + 1而不是left = mid； - 当
x[mid] > target时，mid所在位置不是目标值，right又是闭区间本身具有意义，因此right = mid - 1而不是right = mid
- 结束条件为
- 当在[left,right)中查找目标值时，
left=right无意义(理解为[1,1)是有无意义的)，因此可以忽略掉。- 结束条件为
for left < right； - 当
x[mid] < target时，mid所在位置不是目标值，left又是闭区间本身是具有意义，因此left = mid + 1而不是left = mid； - 当
x[mid] > target时，mid所在位置不是目标值，同时right是开区间本身无意义，因此right = mid而不是right = mid-1(如果right = mid - 1那么mid-1就不会被查找到)
- 结束条件为
代码：
func search(nums []int, target int) int {
left,right := 0,len(nums)
for left < right { // 左闭右开
mid := left + ((right - left) >> 1) // 取中间值优化版
if nums[mid] == target { // 找到目标值返回位置
return mid
}
if nums[mid] < target {
left = mid + 1
}else if nums[mid] > target {
right = mid
}
}
return -1 // 没有找到值返回-1
}
补充：
有两点可以优化的地方：
(right + left) / 2的操作可以用位运算来进行会优化一点(right + left) >> 1。right + left的操作可能会超出数据范围，因此可以left + ((right - left) >> 1)用减法再加法来避免。
题目：27. 移除元素
思路：
双指针法解决问题，慢指针实际上维护的是一个没有目标元素的数组(逻辑上)，而快指针是遍历先前的数组。因此当快指针遍历到目标元素时，慢指针不采取任何行动因为自己的数组中不存在该元素；当元素不是目标元素时，慢指针维护自己的数组。
因为慢指针在快指针左侧，所以不会影响到先前数组的元素，不需要担心。
代码：
func removeElement(nums []int, val int) int {
l := 0 // 慢指针
lens := len(nums) // 元素数量
for r := 0; r < len(nums); r++ { // 遍历指针(快指针)
if nums[r] == val { // 如果等于那就元素数量-1，慢指针不动
lens--
continue
}
nums[l] = nums[r] // 如果不等于把快指针的值赋给慢指针
l++
}
nums = nums[:lens] // 删除多余的元素
return lens
}