黑马程序员技术交流社区

标题: 二分查找求详细讲解一下。 [打印本页]

---

作者: 王少雷    时间: 2013-3-6 10:34
标题: 二分查找求详细讲解一下。


Arrays.binarySearch(new int[]{1,3,4}, 2); -2
Arrays.binarySearch(new int[]{1,2,3}, 2); 2
Arrays.binarySearch(new int[]{1,2,3}, 1); 0
API中：
返回：
如果它包含在数组中，则返回搜索键的索引；否则返回 (-(插入点) - 1)。插入点 被定义为将键插入数组的那一点：即第一个大于此键的元素索引，如果数组中的所有元素都小于指定的键，则为 a.length。注意，这保证了当且仅当此键被找到时，返回的值将 >= 0。
  依照这个工作，原理，有人能说一下内部算法吗。

---

作者: 杨杨    时间: 2013-3-6 11:27
public static int binarySearch(int[] a, int key) {
        return binarySearch0(a, 0, a.length, key);
    }
private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                     int key) {
        int low = fromIndex;//数组下标而不是 数组的值
        int high = toIndex - 1;//数组下标而不是 数组的值

        while (low <= high) {
            int mid = (low + high) >>> 1;//如果我写的话(low+high)/2 学习了 人家写的就是好啊 效率问题
            int midVal = a[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }

---

作者: 黄欢    时间: 2013-3-6 11:37
你可以去看下数据结构。这个上面这些方法很多。

二分法查找的原理就是：
  数据是按升序排列。
  用序列最大和序列最小相加除以2以后用此数与你需要查找的数比较大小。如果大于中间数则到后半段继续之前的操作。直到找到其为止!

---

作者: 张洪慊    时间: 2013-3-6 15:15


我以前的总结,关键看两个查找过程
/*        
折半(二分)查找:      
算法思想:
要求序列必须有序(升序/降序),因为只有这样才能确定数据的范围,通过不断的折半来缩小查找数据的范围         
设查找数据为key
①通过两个变量min和max来指定数据的范围,要求min<=max (min=max表示只有一个数据时)         
②首先与mid=(min+max)/2比较,如果key=mid查找成功,直接返回mid,如果key<mid,则min=mid-1,缩短查找范围,此时在让key与mid=(max+min)/2比较,若key>mid,
则max=mid+1,之后再与新的mid比较,依次类推找到则返回,未找到则min>max.
*/
1.找到(图形代表查找过程mid,min,max值的变化)

以上0,1...代表数组下标
2.未找到:

---

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

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