二分查找/折半查找
二分查找算法
二分查找：
请对一个有序数组进行二分查找 {1,8, 10, 89, 1000, 1234} ，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示"没有这个数"。
课后思考题：
{1,8, 10, 89, 1000, 1000，1234}当一个有序数组中，有多个相同的数值时，如何将所有的数值都查找到，比如这里的 1000.
二分查找的思路分析
- 首先确定该数组的中间的下标
mid = (left + right) / 2 - 然后让需要查找的数 findVal 和 arr[mid] 比较
- findVal > arr[mid] , 说明你要查找的数在mid 的右边, 因此需要递归的向右查找
- findVal < arr[mid], 说明你要查找的数在mid 的左边, 因此需要递归的向左查找
- findVal == arr[mid] 说明找到，就返回
什么时候我们需要结束递归.
1) 找到就结束递归 2) 递归完整个数组，仍然没有找到findVal ，也需要结束递归 当 left > right 就需要退出
这个在用之前不是要排序么???
所以这个使用二分查找的条件是这个数组必须是有序的