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

Question

我正在努力调整 codaddict在这里提出的代码来解决这个问题的简单变体。有人有想法吗？

Answer 1

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

迈克尔安德森关于你所指的算法是如何编写的是正确的，但它很容易适应。

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();
}

Answer 2

这是一种二分查找的采用。

#include <list>
#include <iostream>

int arr[9]={0,1,2,3,4,5,7,7,8};

/*int * array - where to search
  int numberOfElements - the number of elements in array
  int targetValue - the value that we are looking for 
*/

int find( int * array, int numberOfElements, int targetValue)
{
    //we start with searching in the whole array (this is our "scope").
    int left = 0;
    int right = numberOfElements;

    while(left < right)
    {
        //We take the middle item of our "scope" and compare it with the target value.
        int mid = (left + right) / 2;
        if( array[ mid ] >= targetValue)//If we did hit
        {
            //we check is it the first item to match our criteria.              
            if(array[ mid - 1 ] < targetValue)
            {
                //If it is, we return the index.
                return mid;
            }
            else
            { 
                //Else, we continue searching to the left. 
                right = mid;
            }
        }
        //If we didnt hit from the first guess, we continue with our "scope"
        //being either the left of the right half of the previous "scope".
        else if( array[mid] > targetValue )
            right = mid;
        else
            left = mid;
     }
}

int main()
{
    std::cout << find(arr, 9, 7);
}

output: 3

Answer 3

要找到需要修改结束条件的第一个索引，以检查它是否真的是满足条件的第一个索引i：X[i] >= a

public int findIndex(int[] array, int target) {
    int left = 0;
    int right = array.length;
    while (left < right) {
        int mid = (left + right) / 2;
        if (array[mid] >= target && (mid == 0 || array[mid - 1] < target)) {
            return mid;
        } else if (array[mid] > target) {
            right = mid;
        } else
            left = mid;
    }
    return -1;
}