场景:
一组数字类型的数据,给出一个数字,求出数字对应的索引
例如:
int[] arr=new int[]{1,2,3,4,10,20,30,50,90,100}
我们要求55对应的索引位置。
假设arr数组中存储是数字范围的起始值(按范围求索引也可以应用此算法场景)
那么索引对值的表格为:
索引 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
值 | 1 | 2 | 3 | 4 | 10 | 20 | 30 | 50 | 90 | 100 |
·
我们使用二分法来求出50对应应该所在索引位置
一、实例解析
算法如下所示
int SearchInd(long[] ipArray, int start, int end ,long vl) //(二分法) { int middle = (start + end) / 2; if (middle == start) return middle; else if (vl < ipArray[middle]) return SearchInd(ipArray, start, middle, vl); else return SearchInd(ipArray, middle, end, vl); }
运行过程如下所示:
1-10:middle=5 55>arr[5]
5-10:middle=7 55>arr[7]
7-10:middle=8 55>arr[8]
8-10:middle=9 55<arr[9]
8-9:middle=8 Statr=middle
return middle;
得到了正确的结果55在50-90之间,那么他在数组中的位置就是8
5次递归后得到正确结果,如果使用遍历的话需要8次才能得到索引位置。
于是我们得出了这样的结论:
在由小到大的有序数字队列中,要查找的值 vl >arr[middle] 则应从 middle-->End之间继续查找,反之则从Statr-middle中查找vl
也可以说成,要查找的值 vl<arr[middle] 则应从Statr-middle之间查找,反之则从middle-End之间查找vl
二、二分法介绍
二分法使用参考 https://www.cnblogs.com/wanglog/p/6650695.html