使用具有重複項的排序數組的二進制搜索

Question

我的任務是創建一個方法，該方法將打印排序數組中找到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」

Answer 1

好，如果你實際上有一個排序數組，你可以進行二分搜索，直到找到你正在查找的索引之一，然後從那裏開始，其餘的應該很容易找到，因爲它們都是彼此相鄰的。

一旦你找到你的第一個，比你先找到所有的實例，然後找到它之後的所有實例。

使用你應該得到這個方法大致O（LG電子（N）+ K）其中ķ是，你要搜索的值的出現次數。

編輯：

而且，不，你將永遠無法訪問任何東西都ķ值小於O（K）時間。

第二個編輯：，這樣我可以感覺好像我確實有助於一些有用的東西：

而不是隻是在尋找X的第一個和最後一個出現比你可以做一個二進制搜索第一次出現以及二進制搜索最後一次出現。這將導致總計O（lg（n））。一旦你做到了這一點，你就會知道，所有的指標之間還包含X（假設它排序）

您可以通過搜索檢查是否值等於X，和檢查做到這一點如果左邊（或右邊的值）取決於您是要查找第一次還是最後一次出現）等於x。

Answer 2

如果您不需要使用二分查找，則哈希表可能有效。

創建一個HashMap，其中Key是其本身的值，然後value是該值位於數組中的索引數組。循環訪問數組，每個值更新HashMap中的每個數組。

每個值的索引查找時間將爲〜O（1），並且創建映射本身將爲〜O（n）。

Answer 3

public void printCopies(int[] array) 
{ 
    HashMap<Integer, Integer> memberMap = new HashMap<Integer, Integer>(); 
    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 
} 

Alternatevely，而不是計算出現的次數，你可以把自己的指數在一個ArrayList和提出，在地圖上，而不是數量。我想這將不得不公佈。

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<rightIndex; i++) 
System.out.println(array[i] + "\t"); 

Answer 4

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） 閱讀和理解的代碼。這很簡單。

Answer 5

你將得到的結果在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); 
     } 
    } 
} 

Answer 6

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）中。

Answer 7

下面是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; 
} 

Answer 8

。它將是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; 
     } 
    } 

Answer 9

log（n）二進制搜索最左側目標和最右側目標的另一個結果。這是用C++編寫的，但我認爲它很可讀。

這個想法是，我們總是最終在left = right + 1。因此，要找到最左邊的目標，如果我們可以將right移動到小於目標的最右邊的數字，則左邊將位於最左邊的目標。

對於最左邊的目標：

int binary_search(vector<int>& 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<int>& 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; 
} 

Answer 10

我使用二進制搜索想出了一個解決辦法，唯一的事情是做二進制如果找到匹配，則搜索雙方。

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 = (h-l)/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）複雜度的結果。