使用带有重复项的已排序数组的二进制搜索
我的任务是创建一个方法，打印所有索引，其中值x在排序数组中找到。
据我所知，如果我们只是从0到N（数组长度）扫描数组，那么它的运行时间最短为O（n）。 由于将传递给方法的数组将被排序，我假设我可以利用二进制搜索，因为这将是O（log n）。 但是，这仅在数组具有唯一值时才有效。 由于二进制搜索将在第一次“查找”特定值之后完成。 我正在考虑进行二进制搜索以在排序数组中查找x，然后检查此索引之前和之后的所有值，但是如果数组包含所有x值，那么它似乎不会更好。
我想我要问的是，有没有更好的方法来找到排序数组中特定值的所有索引，该索引优于O（n）？
public void PrintIndicesForValue42(int[] sortedArrayOfInts) { // search through the sortedArrayOfInts // print all indices where we find the number 42. } 例如：sortedArray = {1,13,42,42,42,77,78}将打印：“在指数中发现42：2,3,4”
好吧，如果你确实有一个排序数组，你可以进行二进制搜索，直到你找到一个你正在寻找的索引，从那里，其余的应该很容易找到，因为它们都在每个旁边 – 其他。
一旦你找到了第一个，你就会找到它之前的所有实例，然后找到它之后的所有实例。
使用该方法，您应该大致得到O（lg（n）+ k） ，其中k是您要搜索的值的出现次数。
编辑：
而且，不，你永远无法在O（k）时间内访问所有k值。
第二次编辑：这样我觉得好像我实际上贡献了一些有用的东西：
而不是只搜索X的第一次和最后一次出现，而不是搜索第一次出现的二进制搜索和最后一次出现的二进制搜索。 这将导致总计O（lg（n）） 。 一旦你完成了，你就会知道所有索引之间也包含X（假设它已经排序）
您可以通过搜索检查值是否等于x来执行此操作，并检查左侧（或右侧取决于您是查找第一次出现还是最后一次出现）的值是否等于x 。
你会得到O（lg n）的结果
public static void PrintIndicesForValue(int[] numbers, int target) { if (numbers == null) return; int low = 0, high = numbers.length - 1; // get the start index of target number int startIndex = -1; while (low <= high) { int mid = (high - low) / 2 + low; if (numbers[mid] > target) { high = mid - 1; } else if (numbers[mid] == target) { startIndex = mid; high = mid - 1; } else low = mid + 1; } // get the end index of target number int endIndex = -1; low = 0; high = numbers.length - 1; while (low <= high) { int mid = (high - low) / 2 + low; if (numbers[mid] > target) { high = mid - 1; } else if (numbers[mid] == target) { endIndex = mid; low = mid + 1; } else low = mid + 1; } if (startIndex != -1 && endIndex != -1){ for(int i=0; i+startIndex<=endIndex;i++){ if(i>0) System.out.print(','); System.out.print(i+startIndex); } } }
public void PrintIndicesForValue42(int[] sortedArrayOfInts) { int index_occurrence_of_42 = left = right = binarySearch(sortedArrayOfInts, 42); while (left - 1 >= 0) { if (sortedArrayOfInts[left-1] == 42) left--; } while (right + 1 < sortedArrayOfInts.length) { if (sortedArrayOfInts[right+1] == 42) right++; } System.out.println("Indices are from: " + left + " to " + right); }
这将在O（log（n）+ #occurrences）中运行。阅读并理解代码。 这很简单。
如果您不需要使用二进制搜索，则Hashmap可能有效。
创建一个HashMap，其中Key是值本身，然后value是索引数组，其中该值在数组中。 循环遍历数组，为每个值更新HashMap中的每个数组。
每个值的索引的查找时间将是~O（1），并且创建映射本身将是~O（n）。
Find_Key(int arr[], int size, int key){ int begin = 0; int end = size - 1; int mid = end / 2; int res = INT_MIN; while (begin != mid) { if (arr[mid] < key) begin = mid; else { end = mid; if(arr[mid] == key) res = mid; } mid = (end + begin )/2; } return res; }
假设整数数组按升序排序; 返回键出现的第一个索引或INT_MIN的索引。 在O（lg n）中运行。
下面是java代码，它返回搜索键在给定排序数组中传播的范围：
public static int doBinarySearchRec(int[] array, int start, int end, int n) { if (start > end) { return -1; } int mid = start + (end - start) / 2; if (n == array[mid]) { return mid; } else if (n < array[mid]) { return doBinarySearchRec(array, start, mid - 1, n); } else { return doBinarySearchRec(array, mid + 1, end, n); } } /** * Given a sorted array with duplicates and a number, find the range in the * form of (startIndex, endIndex) of that number. For example, * * find_range({0 2 3 3 3 10 10}, 3) should return (2,4). find_range({0 2 3 3 * 3 10 10}, 6) should return (-1,-1). The array and the number of * duplicates can be large. * */ public static int[] binarySearchArrayWithDup(int[] array, int n) { if (null == array) { return null; } int firstMatch = doBinarySearchRec(array, 0, array.length - 1, n); int[] resultArray = { -1, -1 }; if (firstMatch == -1) { return resultArray; } int leftMost = firstMatch; int rightMost = firstMatch; for (int result = doBinarySearchRec(array, 0, leftMost - 1, n); result != -1;) { leftMost = result; result = doBinarySearchRec(array, 0, leftMost - 1, n); } for (int result = doBinarySearchRec(array, rightMost + 1, array.length - 1, n); result != -1;) { rightMost = result; result = doBinarySearchRec(array, rightMost + 1, array.length - 1, n); } resultArray[0] = leftMost; resultArray[1] = rightMost; return resultArray; }
它使用修改的二进制搜索。 它将是O（LogN）。 空间复杂度将为O（1）。 我们两次调用BinarySearchModified。 一个用于查找元素的起始索引，另一个用于查找元素的结束索引。
private static int BinarySearchModified(int[] input, double toSearch) { int start = 0; int end = input.Length - 1; while (start <= end) { int mid = start + (end - start)/2; if (toSearch < input[mid]) end = mid - 1; else start = mid + 1; } return start; } public static Result GetRange(int[] input, int toSearch) { if (input == null) return new Result(-1, -1); int low = BinarySearchModified(input, toSearch - 0.5); if ((low >= input.Length) || (input[low] != toSearch)) return new Result(-1, -1); int high = BinarySearchModified(input, toSearch + 0.5); return new Result(low, high - 1); } public struct Result { public int LowIndex; public int HighIndex; public Result(int low, int high) { LowIndex = low; HighIndex = high; } }
我想出了使用二进制搜索的解决方案，如果找到匹配，唯一的办法是在两边进行二进制搜索。
public static void main(String[] args) { int a[] ={1,2,2,5,5,6,8,9,10}; System.out.println(2+" IS AVAILABLE AT = "+findDuplicateOfN(a, 0, a.length-1, 2)); System.out.println(5+" IS AVAILABLE AT = "+findDuplicateOfN(a, 0, a.length-1, 5)); int a1[] ={2,2,2,2,2,2,2,2,2}; System.out.println(2+" IS AVAILABLE AT = "+findDuplicateOfN(a1, 0, a1.length-1, 2)); int a2[] ={1,2,3,4,5,6,7,8,9}; System.out.println(10+" IS AVAILABLE AT = "+findDuplicateOfN(a2, 0, a2.length-1, 10)); } public static String findDuplicateOfN(int[] a, int l, int h, int x){ if(l>h){ return ""; } int m = (hl)/2+l; if(a[m] == x){ String matchedIndexs = ""+m; matchedIndexs = matchedIndexs+findDuplicateOfN(a, l, m-1, x); matchedIndexs = matchedIndexs+findDuplicateOfN(a, m+1, h, x); return matchedIndexs; }else if(a[m]>x){ return findDuplicateOfN(a, l, m-1, x); }else{ return findDuplicateOfN(a, m+1, h, x); } } 2 IS AVAILABLE AT = 12 5 IS AVAILABLE AT = 43 2 IS AVAILABLE AT = 410236578 10 IS AVAILABLE AT =
我认为这仍然提供O（logn）复杂度的结果。
public void printCopies(int[] array) { HashMap memberMap = new HashMap(); for(int i = 0; i < array.size; i++) if(!memberMap.contains(array[i])) memberMap.put(array[i], 1); else { int temp = memberMap.get(array[i]); //get the number of occurances memberMap.put(array[i], ++temp); //increment his occurance } //check keys which occured more than once //dump them in a ArrayList //return this ArrayList }
或者，不是计算出现次数，而是将它们的索引放在一个arraylist中，然后将其放在地图而不是计数中。
HashMap> //the integer is the value, the arraylist a list of their indices public void printCopies(int[] array) { HashMap> memberMap = new HashMap>(); for(int i = 0; i < array.size; i++) if(!memberMap.contains(array[i])) { ArrayList temp = new ArrayList(); temp.add(i); memberMap.put(array[i], temp); } else { ArrayList temp = memberMap.get(array[i]); //get the lsit of indices temp.add(i); memberMap.put(array[i], temp); //update the index list } //check keys which return lists with length > 1 //handle the result any way you want }
嘿，我想这必须发布。
int predefinedDuplicate = //value here; int index = Arrays.binarySearch(array, predefinedDuplicate); int leftIndex, rightIndex; //search left for(leftIndex = index; array[leftIndex] == array[index]; leftIndex--); //let it run thru it //leftIndex is now the first different element to the left of this duplicate number string for(rightIndex = index; array[rightIndex] == array[index]; rightIndex++); //let it run thru it //right index contains the first different element to the right of the string //you can arraycopy this [leftIndex+1, rightIndex-1] string or just print it for(int i = leftIndex+1; i
log（n）二进制搜索最左边目标和最右边目标的另一个结果。 这是用C ++编写的，但我认为它非常易读。
我们的想法是，当left = right + 1时，我们总是会结束。 因此，为了找到最左边的目标，如果我们可以right移动到最小数目，小于目标，则左边将是最左边的目标。
对于最左边的目标：
int binary_search(vector& nums, int target){ int n = nums.size(); int left = 0, right = n - 1; // carry right to the greatest number which is less than target. while(left <= right){ int mid = (left + right) / 2; if(nums[mid] < target) left = mid + 1; else right = mid - 1; } // when we are here, right is at the index of greatest number // which is less than target and since left is at the next, // it is at the first target's index return left; }
对于最右边的目标，这个想法非常相似：
int binary_search(vector& nums, int target){ while(left <= right){ int mid = (left + right) / 2; // carry left to the smallest number which is greater than target. if(nums[mid] <= target) left = mid + 1; else right = mid - 1; } // when we are here, left is at the index of smallest number // which is greater than target and since right is at the next, // it is at the first target's index return right; }