2

nums[n]などの数値の配列があります。keyよりも小さいすべての整数の中でnums[i]が最大になるような位置'i'を見つける必要があります。numsはソートされています。i=0からnums[i]>=keyの位置までの線形検索を使用してこれを実行できることを私は知っています。しかし、私はそれをより速くやりたいので、誰かが必要な二分探索をアルゴに伝えることができますか？

例：nums []={2,4,14,25}およびkey=15。したがって、14は15未満の他のすべての整数の中で最大の整数であるため、iは2である必要があります。

4

2 に答える 2

3

通常の二分探索コードでは、使用される低変数と高変数は配列のインデックスを示すため、位置を簡単に知ることができます。

まず、a [0]> = keyかどうかを確認します。これは、検索するためのキーよりも少なくとも1要素少ない要素が必要だからです。

次に、二分探索に進みます。中央の要素を取り出します。この要素が> = keyの場合は、それを含むその右側のすべての要素を破棄します。

ただし、[mid]<キーの場合は、その左側にあるすべての要素（それを含む）を破棄し、現在までに見つかった要素またはこの要素の最大値を取り出します。

コード：

    if(a[0]>=key)
    print("Some error message");
    int found=-1;
    int low=0,high=n-1;
    while(low<high)
    {
    int mid=(low+high)/2;
    if(a[mid]>=key)
       high=mid-1;
    else
    {
       low=mid+1;
       found=max(found,a[mid]);
    }

  }

これで、このループの後、lowはhighに等しくなるため、print（low）またはprint（high）であることがわかります。

于 2012-11-07T21:04:36.927 に答える
3

ウェインの方法は正しいです、私はコードのいくつかの変更を加えました。私のコードはJavaです。

<= nums [mid]の場合、キー以上のすべての数値が削除され、highがmid-1に割り当てられます。したがって、ループが終了すると、highはkeyまたは-1よりも小さい最初の数値になります。-1は、指定された配列の数値がキーよりも小さいことを意味します。

public static int lessThan(int[] nums, int key){
    if(nums == null || nums.length == 0) return -1;
    int low = 0, high = nums.length -1;
    while(low <= high){
        int mid = (low + high) >> 1;
        if(key <= nums[mid]){
            high = mid - 1;
        }else {
            low = mid +1;
        }
    }
    return high;
}
于 2012-11-08T04:08:12.137 に答える