普通遍历寻找相当于从第一个数到最后一个数一个一个看过去，比如要从数组{1，2，3，4，……，99，100}100个元素中找到“100”，你要从1开始，看看它是不是等于100，之后2，3，4，一直到100，需要大量的运算时间和内存。
二叉树寻找相当于湖南卫视的那个猜数字游戏，嘉宾说一个范围，游戏要求答题人需要在这个范围内猜到正确的数字，嘉宾在答题人说出数字后会提示大小，比如第一场游戏答案为89
答题人报 70 “小了”
答题人报 90 “大了”
这时答案就在70到90之间，大大减少了运算量。
例题：
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
int firstBadVersion(int n) {
int left = 1, right = n;
while (left < right) { // 循环直至区间左右端点相同
int mid = left + (right - left) / 2; // 防止计算时溢出
if (isBadVersion(mid)) {
right = mid; // 答案在区间 [left, mid] 中
} else {
left = mid + 1; // 答案在区间 [mid+1, right] 中
}
}
// 此时有 left == right，区间缩为一个点，即为答案
return left;
}
------------------------------------------------------------------------------------------
例题：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
示例 4:
输入: nums = [1,3,5,6], target = 0
输出: 0
示例 5:
输入: nums = [1], target = 0
输出: 0
答： 由于题目要求时间复杂度为O(logn),所以使用二分法。
首先用二分法查找目标元素。
如果找到则直接返回下标。
如果数组中没有目标元素则最后将结束while循环，在结束前的最后一次执行while循环时middle,left,right肯定相等。
此时如果nums[middle]<target，则left将等于middle+1，此时target应该大于nums[middle]，小于nums[middle+1]，则应该插入在二者中间，下标变为middle+1=left。而如果nums[middle]>target，则right将等于middle-1，此时target应该大于nums[middle-1]，小于nums[middle]，则应该插入在二者之间，下标变为middle=left。由此可见，当数组中没有目标元素时，插入后目标元素下标始终等于left。
int searchInsert(int* nums, int numsSize, int target){
int left = 0;
int right = numsSize - 1;
while(left <= right){
int middle = (left + right) / 2;
if(nums[middle] > target){
right = middle - 1;
}
else if(nums[middle] < target){
left = middle + 1;
}
else{
return middle;
}
}
return left;