如何使用二進制搜索查找排序數組中的重複項？

Question

我試圖通過重置高變量來擴展函數來查找通過二進制搜索整數匹配的數量，但它被卡在循環中。我猜測一個解決方法是複製此函數以獲取最後一個索引來確定匹配的數量，但我不認爲這將是一個優雅的解決方案。

從這：

public static Matches findMatches(int[] values, int query) { 
    int firstMatchIndex = -1; 
    int lastMatchIndex = -1; 
    int numberOfMatches = 0; 

    int low = 0; 
    int mid = 0; 
    int high = values[values.length - 1]; 
    boolean searchFirst = false; 

    while (low <= high){ 
     mid = (low + high)/2; 

     if (values[mid] == query && firstMatchIndex == -1){ 
      firstMatchIndex = mid; 

      if (searchFirst){ 
       high = mid - 1; 
       searchFirst = false; 
      } else { 
       low = mid + 1; 
      } 

     } else if (query < values[mid]){ 
      high = mid - 1; 
     } else { 
      low = mid + 1; 
     }   
    } 

    if (firstMatchIndex != -1) { // First match index is set 
     return new Matches(firstMatchIndex, numberOfMatches); 
    } 
    else { // First match index is not set 
     return new Matches(-1, 0); 
    } 
} 

爲了這樣的事情：

public static Matches findMatches(int[] values, int query) { 
    int firstMatchIndex = -1; 
    int lastMatchIndex = -1; 
    int numberOfMatches = 0; 

    int low = 0; 
    int mid = 0; 
    int high = values[values.length - 1]; 
    boolean searchFirst = false; 

    while (low <= high){ 
     mid = (low + high)/2; 

     if (values[mid] == query && firstMatchIndex == -1){ 
      firstMatchIndex = mid; 

      if (searchFirst){ 
       high = values[values.length - 1]; // This is stuck in a loop 
       searchFirst = false; 
      } 
     } else if (values[mid] == query && lastMatchIndex == -1){ 
      lastMatchIndex = mid; 

      if (!searchFirst){ 
       high = mid - 1; 
      } else { 
       low = mid + 1; 
      } 
     } else if (query < values[mid]){ 
      high = mid - 1; 
     } else { 
      low = mid + 1; 
     } 

    } 

    if (firstMatchIndex != -1) { // First match index is set 
     return new Matches(firstMatchIndex, numberOfMatches); 
    } 
    else { // First match index is not set 
     return new Matches(-1, 0); 
    } 
} 

Answer 1

沒有您的代碼有問題：

high = values[values.length - 1]; 

應該

high = values.length - 1; 

另外你不需要像numberOfMatches和searchFirst這樣的變量，我們可以有相當簡單的解決方案。

現在來解決這個問題，我明白你想要什麼，我認爲二進制搜索適合這樣的查詢。

做所需要的最好的辦法是一旦找到匹配你只是去向前和向後從索引中，直到出現不匹配，這將是既優雅又高效的計算firstMatchIndex和numberOfMatches。

所以，你的功能應該是：

public static Matches findMatches(int[] values, int query) 
{ 
int firstMatchIndex = -1,lastMatchIndex=-1; 
int low = 0,mid = 0,high = values.length - 1; 
while (low <= high) 
{ 
     mid = (low + high)/2; 

     if(values[mid]==query) 
     { 
      lastMatchIndex=mid; 
      firstMatchIndex=mid; 
      while(lastMatchIndex+1<values.length&&values[lastMatchIndex+1]==query) 
      lastMatchIndex++; 
      while(firstMatchIndex-1>=0&&values[firstMatchIndex-1]==query) 
      firstMatchIndex--; 
      return new Matches(firstMatchIndex,lastMatchIndex-firstMatchIndex+1); 
     } 
     else if(values[mid]>query) 
     high=mid-1; 
     else low=mid+1; 
} 
return new Matches(-1,0); 
}   

Answer 2

你不能只是使用類似的一組查找重複？

事情是這樣的：

package example; 

import java.util.ArrayList; 
import java.util.HashSet; 
import java.util.List; 

public class DuplicatesExample { 

    public static void main(String[] args) { 
     String[] strings = { "one", "two", "two", "three", "four", "five", "six", "six" }; 
     List<String> dups = getDups(strings); 
     System.out.println("DUPLICATES:"); 
     for(String str : dups) { 
      System.out.println("\t" + str); 
     } 
    } 

    private static List<String> getDups(String[] strings) { 
     ArrayList<String> rtn = new ArrayList<String>(); 
     HashSet<String> set = new HashSet<>(); 
     for (String str : strings) { 
      boolean added = set.add(str); 
      if (added == false) { 
       rtn.add(str); 
      } 
     } 
     return rtn; 
    } 

} 

輸出：

DUPLICATES: 
    two 
    six 

Answer 3

我已經分手你的問題分爲兩個部分 - 使用二進制搜索，找到一些和計數匹配的數量。

public static Matches findMatches(int[] values, int query) { 

    int leftIndex = -1; 
    int rightIndex = -1; 
    int high = values.length - 1; 

    int matchedIndex = search(values, 0, high, query); 

    //if at least one match 
    if (matchedIndex != -1) { 

     //decrement upper bound of left array 
     int leftHigh = matchedIndex - 1; 
     //increment lower bound of right array 
     int rightLow = matchedIndex + 1; 

     //loop until no more duplicates in left array 
     while (true) { 

      int leftMatchedIndex = search(values, 0, leftHigh, query); 

      //if duplicate found 
      if (leftMatchedIndex != -1) { 
       leftIndex = leftMatchedIndex; 
       //decrement upper bound of left array 
       leftHigh = leftMatchedIndex - 1; 
      } else { 
       break; 
      } 
     } 

     //loop until no more duplicates in right array 
     while(true){ 
      int rightMatchedIndex = search(values, rightLow, high, query); 

      //if duplicate found 
      if(rightMatchedIndex != -1){ 
       rightIndex = rightMatchedIndex; 
       //increment lower bound of right array 
       rightLow = rightMatchedIndex + 1; 
      } else{ 
       break; 
      } 

     } 

     return new Matches(matchedIndex, rightIndex - leftIndex + 1); 

    } 

    return new Matches(-1, 0); 

} 

private static int search(int[] values, int low, int high, int query) { 

    while (low <= high) { 
     int mid = (low + high)/2; 

     if (values[mid] == query) { 
      return mid; 
     } else if (query < values[mid]) { 
      high = mid - 1; 
     } else { 
      low = mid + 1; 
     } 
    } 

    return -1; 

} 

Answer 4

我找到了解決與校正復位導致無限循環高可變出錯後：第一部分由搜索功能，而第二部分是由findMatches功能解決解決。

public static Matches findMatches(int[] values, int query) { 
    int firstMatchIndex = -1; 
    int lastMatchIndex = -1; 
    int numberOfMatches = 0; 

    int low = 0; 
    int mid = 0; 
    int high = values.length - 1; 

    while (low <= high){ 
     mid = (low + high)/2; 

     if (values[mid] == query && firstMatchIndex == -1){ 

      firstMatchIndex = mid; 
      numberOfMatches++; 
      high = values.length - 1; 
      low = mid; 

     } else if (values[mid] == query && (lastMatchIndex == -1 || lastMatchIndex != -1)){ 

      lastMatchIndex = mid; 
      numberOfMatches++; 

      if (query < values[mid]){ 
       high = mid - 1; 
      } else { 
       low = mid + 1; 
      } 

     } else if (query < values[mid]){ 
      high = mid - 1; 
     } else { 
      low = mid + 1; 
     } 
    } 

    if (firstMatchIndex != -1) { // First match index is set 
     return new Matches(firstMatchIndex, numberOfMatches); 
    } 
    else { // First match index is not set 
     return new Matches(-1, 0); 
    } 
} 

Answer 5

除了排序先驗之外，沒有關於數據的任何知識是很難的。 看到這個： Binary Search O(log n) algorithm to find duplicate in sequential list?

這將找到排序數組中k的重複索引。 當然，這與知道首先重複的值有關，但在已知時非常有用。

public static int searchFirstIndexOfK(int[] A, int k) { 

    int left = 0, right = A.length - 1, result = -1; 
    // [left : right] is the candidate set. 
    while (left <= right) { 
     int mid = left + ((right - left) >>> 1); // left + right >>> 1; 
     if (A[mid] > k) { 
     right = mid - 1; 
     } else if (A[mid] == k) { 
     result = mid; 
     right = mid - 1; // Nothing to the right of mid can be 
               // solution. 
     } else { // A[mid] < k 
     left = mid + 1; 
     } 
    } 
    return result; 
    } 

這會找到的log（n）時間愚弄的人，但在數據必須進行排序，以及1和範圍1..N越來越脆弱。

static int findeDupe(int[] array) { 
int low = 0; 
int high = array.length - 1; 
while (low <= high) { 
    int mid = (low + high) >>> 1; 
    if (array[mid] == mid) { 
    low = mid + 1; 

    } else { 
    high = mid - 1; 

    } 

} 
System.out.println("returning" + high); 
return high; 

}