java - 对带有字符串前缀的数组进行二分搜索

Question

我如何使用二进制搜索将包含特定字符串前缀的排序数组的元素添加到数组列表中，并将这些元素按照它们在数组中出现的顺序添加。

编码并不难，但我在二进制搜索方面遇到了困难。要使用字符串前缀，String 类提供了 startswith。我只需要帮助来开始二进制搜索

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

}

Answer 1

使用 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));
        }
}