java - 在排序数组 X 中搜索第一个索引 i 使得 X[i] >= a

Question

我正在努力调整 codaddict proposed here 找到的代码解决这个问题的简单变体。有人有想法吗？

Answer 1

你采用他的算法，并返回 high 而不是 -1。如果 X[high] 小于您的目标，则取下一个项目。如果 high 等于您的数组大小，则没有这样的索引。

Michael Anderson 关于您指出的算法的编写方式是正确的，但它很容易适应。

int find_hi (const std::vector<int> &X, int t) {
   int low  = 0;
   int high = X.size() - 1;
   while(low <= high) {
       int mid = (low + high) / 2;
       if(X[mid] == t) return mid;
       else if(X[mid] < t)
           low = mid + 1;
       else
           high = mid - 1;
   }
   if (high < sz && X[high] < t) ++high;
   return high;
}

但是，这等同于 C++ 中的以下内容:

int find_hi (const std::vector<int> &X, int t) {
    return std::lower_bound(X.begin(), X.end(), t) - X.begin();
}