黑马程序员技术交流社区

标题: 数组的折半查找 [打印本页]

---

作者: Java_Bird    时间: 2015-9-8 21:41
标题: 数组的折半查找
前提：数组必须有序  
只要中间索引对应的值与传入的值不相等就拿中间索引对应的值和传入的值比较
如果中间索引对应的值比传入的值大，那么最大索引就应该是中间索-1(因为已经确定不是中间索引个)
如果中间缩影对应的值比传入的小，那么最小索引就应该是中间索引+1(因为已经确定不是中间索引个)
为什么要+1,-1,因为中间缩影对应的值不等于传入的值，
在下次遍历的时候就可以忽略该索引

最后判断最小值是否最大值  

public static intgetIndex(int[] arr, int value) {

              intmaxIndex = arr.length - 1;// 定义最大索引

              intminIndex = 0;// 定义最小索引

              intmidIndex = (maxIndex + minIndex) / 2;// 定义中间索引

              while(arr[midIndex] != value) {

                     if (arr[midIndex] > value) {

                            maxIndex = midIndex - 1;

                     } else if (arr[midIndex] < value) {

                            minIndex = midIndex + 1;

                     }

                     // 如果数据不存在。

                     if (minIndex > maxIndex) {

                            return -1;

                     }

                     // 下一次二分查找开始

                     midIndex = (maxIndex + minIndex) / 2;

              }

              returnmidIndex;

       }

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2