二分法查找数字在数组中的索引,确定数字对应的索引

场景:

一组数字类型的数据,给出一个数字,求出数字对应的索引

例如:

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

 

上一篇:[Planetbase Help Doc] Camera


下一篇:java 学习笔记-基础算法(七)