主页 / 问题 / 1113752
Accepted
Str
Asked:2020-04-22 05:38:49 +0000 UTC2020-04-22 05:38:49 +0000 UTC

查找数组中的所有元素

  • 772

我在网上找不到的问题（这并不奇怪，因为很多人使用现成的方法）是如何使用二进制搜索找到数组中所有相同的元素？如果我将二进制搜索限制for-ом在找到的第一个元素并通过提高左“底部”直到返回“”来“遍历”二进制搜索，那么二进制搜索是否会是二进制的нет найденных элементов？

或者它可以以其他方式完成而不诉诸于for？告诉！

搜索最左边的元素 -

public static int binary_search_leftmost(int[] A,int n,int T) {
        int L = 0;
        int R = n;
        while (L < R) {
            int m = ((L + R) / 2);
            if (A[m] < T){
                L = m + 1;
            } else {
                R = m;
            }
        }
        return L;
}
    public static void main(String [] args) {
        int[] arr = {1,2,3,4,5,5,5,5,6,6,6,7,7,7,7,8,8,8,8,9,9,9};
        System.out.println(binary_search_leftmost(arr,17,5));
    }

添加 -

static int binarySearchR(String[] arr, String x) 
    { 
        int l = 0, r = arr.length - 1; 
        while (l < r) { 
            int m = l + (r - l) / 2; 

            int res = x.compareTo(arr[m]); 

            if (res == 0) 
                return m; 

            if (res < 0) 
                r = m - 1;

            else
                 l = m + 1; ; 
        } 

        return -1; 
    }

我不明白如何修复它以便找到最右边的元素..如果元素是2，那么它会找到第二个，但是如果有3个或更多元素，那么该方法仍然只找到第二个元素第一个 .. 例如：{"aa","aa","aa","aa","bb","bb"}- 该方法查找索引为 1 的元素，需要查找索引为 3 的元素

java

1 个回答

  1. Best Answer
    public static int BSL(String A[], String key) 
{ 
    int m; 
    int l = 0, r = A.length; 

    while( r > l ) 
    { 
        m = l + (r - l)/2; 

        if( A[m].compareTo(key) < 0 ) 
            l = m + 1; 
        else
            r = m; 
    } 

    return l; 
} 

public static int BSR(String A[], String key) 
{ 
    int l = 0, r = A.length; 
    int m; 

    while( r > l) 
    { 
        m = l + (r - l)/2; 

        if( A[m].compareTo(key) > 0 ) 
            r = m; 
        else
            l = m + 1; 
    } 
    return r - 1; 

}

    public static void main (String[] args) throws java.lang.Exception
    {
       String[] arr = {"aa","aa","bb","bb","bb","cc","cc"};
       int l = BSL(arr, "bb");
       int r = BSR(arr, "bb");
       System.out.println(l);
       System.out.println(r);

    }

    ideone

    2
4

    在第二次搜索中通过已经找到的左边缘稍微有利可图。

    • 1

相关问题