wen 二分查找边学习边写模板
首先根据自己脑子的浆糊先写一个，再来找问题。
int binarySearch(int* nums, int target, int left, int right){
int mid = (left + right) >> 1;
while(l < r){
if(nums[mid] == target){
return target; //如果是返回数组的位置就返回mid( +- 1)
}else if(nums[mid] > target){
//如果当前中间的数字大于目标，
//说明right需要缩小
right = mid;
return binarySearch(nums, target, left, right);
}else if(nums[mid] < target){
left = mid;
return binarySearch(nums, target, left, right);
}
}
return -1;
}
（其实因为数组内是按序排序的，可以先判断target是否小于数组中最小的数或者大于数组中最大的数。
很明显是没有判定左闭右开或者左开右闭还是什么其他情况的，单纯用脑子我自己绕不清，所以我想直接列数据。
首先假定数组中的元素都是从小到大排序的。
先判断数组选择是左闭右闭的情况，假设数组为{0, 1, 2, 3, 4, 5}。我们当前要查找值为3的数在不在数组中。
【第一轮判断】令left = 0, right = 5, 则mid = 2(2.5), nums[2] < 3, 所以要把左边界缩进，left = mid + 1 = 3, (因为现在在判断左闭右闭的情况，所以要让left = mid + 1, mid已经判断过就不再记进去了)。
【第二轮判断】此时left = 3, right = 5, mid = 4, nums[4] > 3, 所以要把右边界缩小， right = mid – 1, (同理，判断过的mid就不算进去了)。
【第三轮判断】此时left = 3, right = 4, mid = 3(3.5), sum[3] = 3。找到了我们需要找的值为3的数在数组中。
所以我们写的while循环应该是l < r, 不然l == r就无法退出循环，可实际上已经获得的准确答案。
再假定数组选择是左闭右开的情况，假设数组为{0, 2, 4, 5, 6}。我们当前要查找值为3的数在不在数组中。
【第一轮判断】令left = 0, right = 5(右开), mid = 2(2.5), nums[2] > 3, 所以要把右边界缩小， right = mid = 2, (因为右开……)。
【第二轮判断】此时left = 0, right = 2, mid = 1, nums[1] < 3, 所以要把左边界缩进，left = mid + 1, (因为左闭……)。
【第三轮判断】此时left = 2, right = 2, mid = 2, nums[2] > 3, 所以要把右边界缩小, right = mid。
这个时候发现好像陷入死循环了，那left = right就意味着while循环也应该写成l < r, 不然退出不了循环。
这个时候我突然想是不是我举例的问题，然后我私底下把以上两种情况的举例交换了一下判断，while语句依然应该用l < r来判断。
暂时不想想左开右闭和左开右开的情况了，感觉也没必要，始终记左闭右闭这种特殊情况也是ok的。
所以我决定暂时先以左闭右闭为模板来写二分查找，代码如下：
int binarySearch(int* nums, int target, int left, int right){
while(l < r){
int mid = ((left + right) >> 2);
//假定数组是从小到大排序的(即升序)
//判断target有没有越界还是写在外面的函数叭……
if(nums[mid] == target){
return target; //返回数组中的位置就返回mid
}else if(nums[mid] > target){
right = mid – 1;
return binarySearch(nums, target, left, right);
}else if(){
left = mid + 1;
return binarySearch(nums, target, left, right);
}
}
return -1;
}
