二分查找
题目描述
题目解析
暴力解法
我们可以从左往右遍历一次数组，如果存在 target 则返回数组的下标，否则返回 -1。
时间复杂度 O(N)，因为没有利用数组有序的特点，每次比较只能舍弃一个要比较的数。
二分查找法
所以我们可以把 [1, 4] 这个区间舍弃掉，直接看 [5, 8]；仅仅拿 4 和 5 比较一次，就干掉了一大片数。
总结
在一个数组中，随便找一个数，拿这个数和 target 进行比较，并且以拿的这个数分成两个区间，比较后舍弃一部分数，然后再从另一个区间的数中，找下一个要和 target 比较的数。
二分查找算法的本质，就是当数组具有'二段性'时，哪怕这个数组是无序的，只要能在这个数组中发现'二段性'，那么也可以使用二分查找。
'二段性'
当我们发现一个规律，然后根据这个规律，选取某一个点，根据这个点，能把数组分成两个区域，根据规律能够有选择地舍弃一部分，进而在另一个部分继续查找的时候，此时，就可以使用二分查找的算法。
我们要从数组中找和 target 进行比较的数，不一定是先从 n/2 的位置开始找，只要找的这个数的点，能把这个区间分成两部分，即满足二段性，进而使用二分查找法。
但是哪怕那么多点可以选择，但是我们都应该先选择 n/2 的位置的点，因为在概率学的数学期望中，我们选择中间的点，时间复杂度是最好的。
nums[mid]< target，left = mid + 1nums[mid]= target，return midnums[mid]> target，right = mid - 1
细节问题
因为当 left = right 的时候，也是要继续判断的，所以 left <= right 为循环判断条件。