java - 使用二分查找插入 ArrayList

Question

因此，此方法会传递一个 Occurences 数组列表，其中每个包含一个字符串和一个频率。频率是这里唯一重要的部分。但我需要做的是使用二分搜索将 arraylist 中的最后一个元素插入到排序位置。每次运行此代码时，插入位置都会打印为-1。我的代码中是否缺少某些内容？

我需要跟踪在二分搜索期间命中的数组中的索引，这应该不会太困难，但会解释返回类型。

public ArrayList<Integer> insertLastOccurrence(ArrayList<Occurrence> occs) {
    ArrayList<Integer> path = new ArrayList<Integer>();

    int targetFreq = occs.get(occs.size()-1).frequency; //gets the frequency of the thing we want to insert

    //if the array is just 1 value, don't do anything
    if(occs.size() == 1){
        return null;
    }

    int start = 0;               // The start of the search region
    int end = occs.size()-2;// The end of the search region is 1 less than the last position
    int position = -1;           // Position of the target

    // While there is still something list left to search and
    // the element has not been found
    while (start <= end && position == -1)  {
      int mid = start + (end - start) / 2;    //int mid = (start + end) / 2;  // Location of the middle
        // Determine whether the target is smaller than, greater than,
        // or equal to the middle element
        if (targetFreq < occs.get(mid).frequency)   {
        // Target is smaller; continue the left half
        end = mid - 1;
        }
        else if (targetFreq > occs.get(mid).frequency)  {
        // Target is larger, continue the right half
        start = mid + 1;
        }
        else  {
        // Found it!
        position = mid;
        }
    }
    System.out.println(position);   
    return path;
}

Answer 1

那么，我这样理解对吗？您有一个除最后一个元素(在 size()-1 处)之外已排序的 ArrayList，并且您想要找到必须在其后插入该元素以重新获得排序属性的索引？

我想，使用所提供的代码，只有当 ArrayList 包含另一个等于最后一个(要插入的)元素的元素时才能找到这样的索引，因为如果 targetFreq 等于所考虑元素之一的频率，则位置仅设置为 mid 。由于从不考虑最后一个元素 (end = size()-2)，因此很可能找不到相等的元素。