在字符串前綴的數組上進行二分法搜索

如何添加包含使用二進制搜索的特定字符串前綴的排序數組的元素以及這些元素作爲它們在ArrayList中出現的順序。在字符串前綴的數組上進行二分法搜索

這是不難編碼，但我有二進制搜索困難。爲了使用字符串前綴，String類提供了startswith。我只是需要幫助才能開始二進制搜索

public static <T extends Comparable<T>> ArrayList prefixMatch(T[] list, 
      String prefix) { 

}

來源

2012-03-02 Karan Singh

也許你可以澄清你的問題一點點......也許還可以添加一個你想要實現什麼輸入和輸出的例子？ – mikera 2012-03-02 02:55:39

我添加方法來完成這不是一種審查..即使有通用的T []列表數組將會是字符串[]，因爲我必須使用二進制搜索來查找該數組中的元素開始與一個特定的前綴.. – 2012-03-02 03:01:30

可能重複[實現二進制搜索與字符串前綴？]（http://stackoverflow.com/questions/9543046/implement-binary-search-with-string-prefix） – 2012-03-08 23:14:42

使用API中的binarySearch方法。

String[] objString = {"a","b","c"}; 
System.out.println(Arrays.binarySearch(objString,"c"));

或者如果你想創建自己的二進制搜索實現。這裏是。

/* BinarySearch.java */ 
public class BinarySearch { 
     public static final int NOT_FOUND = -1; 

     public static int search(int[] arr, int searchValue) { 
       int left = 0; 
       int right = arr.length - 1; 
       return binarySearch(arr, searchValue, left, right); 
     } 

     private static int binarySearch(int[] arr, int searchValue, int left, int right) { 
       if (right < left) { 
         return NOT_FOUND; 
       } 
       /* 
       int mid = mid = (left + right)/2; 
       There is a bug in the above line; 
       Joshua Bloch suggests the following replacement: 
       */ 
       int mid = (left + right) >>> 1; 
       if (searchValue > arr[mid]) { 
         return binarySearch(arr, searchValue, mid + 1, right); 
       } else if (searchValue < arr[mid]) { 
         return binarySearch(arr, searchValue, left, mid - 1); 
       } else { 
         return mid; 
       }    
     } 
} 
public class BinarySearchTest { 

     public static void main(String[] args) { 
       int[] arr = {1, 5, 2, 7, 9, 5}; 
       Arrays.sort(arr); 
       System.out.println(BinarySearch.search(arr, 2)); 
     } 
}

來源

2012-03-02 03:02:43 John

感謝您的幫助，我真的很感激但我需要實現一個二分法搜索一個通用數組（在這種情況下是字符串），它是排序的。然後將startwith或包含特定前綴的元素添加到arraylist中，因爲它們出現在原始通用數組中 – 2012-03-02 03:05:53

API具有'binarySearch（T [] a，int fromIndex，int toIndex，T key，Comparator c）'方法。您可以創建一個比較器並將其傳遞以僅比較前綴。 – John 2012-03-02 07:10:12

我也有類似的要求 - 給字符串數組查找每一個與新的字母開頭的字符串，即對於Africa Angela Beach Bamboo Zorro的指標，我需要的算法，該算法將返回[ 0, 2, 4 ]

我發現有一個修改衆所周知的使用「延遲相等測試」的二進制搜索算法，並且這具有找到確切需要的索引的副作用 - 起始範圍的索引。

你可以在this Wikipedia article中看到它（也有一個非常簡單的例子，基於這個例子我實現了我自己的）。

來源

2013-09-07 22:41:11 dimsuz

在字符串前綴的數組上進行二分法搜索

回答

相關問題