binarySearch在排序前后的使用问题

Question

本帖最后由 xingzhongyouyu 于 2011-08-07 17:37:36 编辑

Answer 1

public static int binarySearch(int[] a,
                               int key)使用二进制搜索算法来搜索指定的 int 型数组，以获得指定的值。必须在进行此调用之前对数组进行排序（通过上面的 sort 方法）。如果没有对数组进行排序，则结果是不明确的。如果数组包含多个带有指定值的元素，则无法保证找到的是哪一个。 参数：
a - 要搜索的数组。
key - 要搜索的值。 
返回：
搜索键的索引，如果它包含在列表中；否则返回 (-(插入点) - 1)。插入点 被定义为将键插入列表的那一点：即第一个大于此键的元素索引，如果列表中的所有元素都小于指定的键，则为 list.size()。注意，这保证了当且仅当此键被找到时，返回的值将 >= 0。

Answer 2

    /**
     * Searches the specified array of ints for the specified value using the
     * binary search algorithm.  The array <strong>must</strong> be sorted (as
     * by the <tt>sort</tt> method, above) prior to making this call.  If it
     * is not sorted, the results are undefined.  If the array contains
     * multiple elements with the specified value, there is no guarantee which
     * one will be found.
     *
     * @param a the array to be searched.
     * @param key the value to be searched for.
     * @return index of the search key, if it is contained in the list;
     *        otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
     *        <i>insertion point</i> is defined as the point at which the
     *        key would be inserted into the list: the index of the first
     *        element greater than the key, or <tt>list.size()</tt>, if all
     *        elements in the list are less than the specified key.  Note
     *        that this guarantees that the return value will be &gt;= 0 if
     *        and only if the key is found.
     * @see #sort(int[])
     */
    public static int binarySearch(int[] a, int key) {
int low = 0;
int high = a.length-1; while (low <= high) {
    int mid = (low + high) >> 1;
    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.
    }看看源码就知道了

Answer 3

System.out.println("index="+index+",num[index]="+num[index]);
你未找到就返回的-1，num[index]异常了，而且二分查找本来就是要排好序的，无序有可能找到有可能找不到