黑马程序员技术交流社区

标题: 关于二分查找法角标越界 [打印本页]

---

作者: 马纵驰    时间: 2012-11-5 14:10
标题: 关于二分查找法角标越界
为什么但我输入大于等于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 14:36
测试了不会出错，数组包越界因为所查找的脚标不再所引起的，与元素的大小无关

---

作者: 黑马贾林栋    时间: 2012-11-5 18:58
binarySearch()中，int end = arr.length;会发生越界，应改为int end = arr.length-1;

---

作者: 李计伟    时间: 2012-11-5 21:22

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. 
   
7. while (low <= high) {
   
8. int mid = (low + high) >>> 1;
   
9. Comparable midVal = (Comparable)a[mid];
   
10. int cmp = midVal.compareTo(key);
    
11. 
    
12. if (cmp < 0)
    
13. low = mid + 1;
    
14. else if (cmp > 0)
    
15. high = mid - 1;
    
16. else
    
17. return mid; // key found
    
18. }
    
19. return -(low + 1); // key not found.
    
20. }

复制代码

这是调用Arrays.binarySearch(a, key)方法的源码
把int end = arr.length;改成int end = arr.length-1;就好了,你要把角标1的数和角标length-1的数折半再和0角标的比较。

---

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

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