algorithm - 二分探索を変更して、キーよりも次に大きい項目を見つけます

Question

検索対象のキーではなく、次に大きな項目のインデックスを返すように、有名な二分探索アルゴリズムを変更したいと考えています。

したがって、4 つのケースがあります。

1. キーがすべての項目より小さい場合、0 を返します。
2. キーがすべてのアイテムより大きい場合、items.length を返します。
3. キーがインデックス x にある場合、x+1 を返します。
4. キーが見つからない場合は、次に大きいキーのインデックスを返します。

例えば：

data = { 1, 3, 5, 7, 9, 11 };

• 0 を検索すると 0 が返されます。
• 11 または 12 を検索すると、6 が返されます。

• 5 または 6 を検索すると 3 が返されます。

  while (low <= high) {
      mid = (low + high) / 2;
      if (data[mid] < val)
          low = mid + 1;
      else if (data[mid] > val)
          high = mid - 1;
      else {
          break;
      }
  }
  

現在、低い値と高い値を調べることで機能しています。そうするための興味深いコードはありますか？

編集 ！！！

これが私がそれを機能させる方法です：

    if (low <= high)
        found = (low + high) / 2 + 1;
    else if (low >= data.length)
        found = data.length ;
    else if (high < 0)
        found = -1;
    else
        found = low;

もっとエレガントな方法を探しています！

編集 II !!!

重複がない場合、このコードは機能します。重複のケースを処理するには、最初の if 条件を変更する必要があります。

if (low <= high)
    found = (low + high) / 2 + 1;

より大きな要素が見つかるまで繰り返します。

Answer 1

1. リスト項目

ここにコードがあります：

• 要素が存在する場合、検索 する要素のインデックスを返します
• 検索された要素が配列に存在しない場合、次に大きな要素のインデックスを返します
• 配列の最大要素より大きい要素が検索された場合は -1 を返します

      public static int ceilSearch(int arr[], int low, int high, int x) {
    int mid;
    if (x <= arr[low])
      return low;
    if (x > arr[high])
      return -1;

    mid = (low + high) / 2; /* low + (high - low)/2 */

    if (arr[mid] == x)
      return mid;

    else if (arr[mid] < x) {
      if (mid + 1 <= high && x <= arr[mid + 1])
        return mid + 1;
      else
        return ceilSearch(arr, mid + 1, high, x);
    } else {
      if (mid - 1 >= low && x > arr[mid - 1])
        return mid;
      else
        return ceilSearch(arr, low, mid - 1, x);
    }
  }