在字符串前缀的数组上进行二分法搜索

如何添加包含使用二进制搜索的特定字符串前缀的排序数组的元素以及这些元素作为它们在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

在字符串前缀的数组上进行二分法搜索

回答

相关问题