A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 马纵驰 中级黑马   /  2012-11-5 14:10  /  1960 人查看  /  3 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

为什么但我输入大于等于78以上的整数时都会出现角标越界

import java.util.Arrays;
class  A
{
        public static void main(String[] args)
        {
                int[] arr = {40, 25, 68, 58, 77, 13, 9, 28, 63};
                sort(arr);
                String str = Arrays.toString(arr);
                System.out.println(str);
                int key = binarySearch(arr,45);
                System.out.println(key);
        }

        public static void sort(int arr[])
        {
                for (int i = 0 ;i < arr.length-1 ;i++ )
                {
                        int minIndex = getMinIndex(arr,i);
                        swap(arr,minIndex,i);
                }
        }


        public static int getMinIndex(int[] arr,int index)
        {
                int minIndex = index;
                for (int i = index+1;i < arr.length ;i++ )
                {
                        if (arr[minIndex] > arr[i])
                        {
                                minIndex = i;
                        }
                }
                return minIndex;
        }

        public static void swap(int[] arr,int minIndex,int index)
        {
                int temp = arr[index];
                arr[index] = arr[minIndex];
                arr[minIndex] = temp;
        }

        public static int binarySearch(int[] arr,int key)
        {
                int begin = 0;
                int end = arr.length;
                int m;

                while (begin <= end)
                {
                        m = (begin + end) / 2;
                        if (key == arr[m])
                        {
                                return m;
                        }
                        if (key > arr[m])
                        {
                                begin = m + 1;
                        }else
                        {
                                end = m - 1;
                        }
                }

                return -1;

        }

       
}

点评

哥们二分查找是要先排好序的  发表于 2012-11-5 21:29

评分

参与人数 1技术分 +1 收起 理由
古银平 + 1 赞一个!

查看全部评分

3 个回复

倒序浏览
测试了不会出错,数组包越界因为所查找的脚标不再所引起的,与元素的大小无关
回复 使用道具 举报
binarySearch()中,int end = arr.length;会发生越界,应改为int end = arr.length-1;
回复 使用道具 举报
  1. // Like public version, but without range checks.
  2. private static int binarySearch0(Object[] a, int fromIndex, int toIndex,
  3. Object key) {
  4. int low = fromIndex;
  5. int high = toIndex - 1;

  6. while (low <= high) {
  7. int mid = (low + high) >>> 1;
  8. Comparable midVal = (Comparable)a[mid];
  9. int cmp = midVal.compareTo(key);

  10. if (cmp < 0)
  11. low = mid + 1;
  12. else if (cmp > 0)
  13. high = mid - 1;
  14. else
  15. return mid; // key found
  16. }
  17. return -(low + 1); // key not found.
  18. }
复制代码
这是调用Arrays.binarySearch(a, key)方法的源码
把int end = arr.length;改成int end = arr.length-1;就好了,你要把角标1的数和角标length-1的数折半再和0角标的比较。

回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马