二分查找/折半查找

二分查找算法

二分查找：

请对一个有序数组进行二分查找 {1,8, 10, 89, 1000, 1234} ，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示”没有这个数”。

课后思考题：

{1,8, 10, 89, 1000, 1000，1234}当一个有序数组中，有多个相同的数值时，如何将所有的数值都查找到，比如这里的 1000.

二分查找的思路分析

1. 首先确定该数组的中间的下标
   mid = (left + right) / 2
2. 然后让需要查找的数 findVal 和 arr[mid] 比较
3. findVal > arr[mid] , 说明你要查找的数在mid 的右边, 因此需要递归的向右查找
4. findVal < arr[mid], 说明你要查找的数在mid 的左边, 因此需要递归的向左查找
5. findVal == arr[mid] 说明找到，就返回

什么时候我们需要结束递归.

1. 找到就结束递归
2. 递归完整个数组，仍然没有找到findVal ，也需要结束递归 当 left > right 就需要退出

这个在用之前不是要排序么???

所以这个使用二分查找的条件是这个数组必须是有序的