9

並べ替えられた数値のリストが与えられた場合、特定の数値よりも大きい最小の数値を見つける必要があります。次のリストを検討してください。

arr=[1,2,3,5,7,11,101,131,151,181,191,313,353,373,383]

指定された数値が 320 であるとします。353 は 320 より大きい最小の数値であるため、メソッドは 353 を返す必要があります。

少し変更した形式のバイナリ検索を使用しようとしています。ただし、実行時にプログラムは無限ループに入ります。

def modBinarySearch(arr,x):
    l=len(arr)
    mid=l/2
    if arr[mid]>=x and arr[mid-1]<x:
        return arr[mid]
    elif arr[mid]>x and arr[mid-1]>x:
        modBinarySearch(arr[mid:l],x)
    else: 
        modBinarySearch(arr[0:mid],x)

N=int(raw_input())
arr=[1,2,3,5,7,11,101,131,151,181,191,313,353,373,383]
print modBinarySearch(arr,N)

誰かが私が間違っていることを指摘できますか?

4

8 に答える 8

11

bisectすでにこれを行う標準モジュール があります。

In [49]: arr[bisect.bisect(arr, 320)]
Out[49]: 353

これは、ソートされたリストを検索するための頼りになる方法だと思います。マニュアルにはいくつかの例があります。

実装に関しては、いくつかの問題があります。

  1. あなたの再帰は小さな配列を正しく処理しません。
  2. 2 番目のブランチで行われたスライスは正しくありません。
  3. あなたの関数は何も返しません。
  4. arrは昇順であるため、とarr[mid]>x and arr[mid-1]>x同等でありarr[mid-1]>x、意図したことを書いていないことを示唆しています

最後になりましたが、再帰とそのすべてのスライスは、この問題にはまったく不要です。

于 2012-12-02T13:42:10.633 に答える
6

リストのサイズが 15 になる場合は、バイナリ検索を完全に捨てて、順次検索を使用します。

コードを書くのははるかに簡単で、毎秒何百万回も実行する必要がない限り、逐次的なソリューションは十分に高速です。

二分探索に固執する必要がある場合、最初のステップは、再帰呼び出しの結果を実際に返すことです。

于 2012-12-02T13:42:06.323 に答える
5

arr[mid] と arr[mid-1] がどちらも自分の数値よりも大きい場合は、arr[0:mid] で検索する必要がありますね。

 elif arr[mid]>x and arr[mid-1]>x:
    modBinarySearch(arr[0:mid],x)
else: 
    modBinarySearch(arr[mid:1],x)
于 2012-12-02T13:51:08.687 に答える
3 
def modBinarySearch(arr, n):
    m = len(arr) / 2

    if arr[m] >= n and arr[m - 1] < n:
        return arr[m]
    elif arr[m] > n and arr[m - 1] > n:
        return modBinarySearch(arr[:m], n)
    else:
        return modBinarySearch(arr[m:], n)


arr = [1, 2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383]
n = 320
print(modBinarySearch(arr, n))
于 2012-12-02T13:49:40.823 に答える
2 
     python 3.2

     next(i for  i in arr if i>320)
于 2012-12-02T13:50:02.917 に答える
1

これにはbisect モジュールが最適です。

from bisect import bisect_left, bisect_right

arr=[1,2,3,5,7,11,101,131,151,181,191,313,353,373,383]


def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

print find_lt(arr,320)          
print find_gt(arr,320)

版画

313
353
于 2012-12-03T17:32:25.883 に答える
0

リストがソートされている場合:

x = range(20)
N= 15

for i in x:
    if i>N:
        print i
        break

16 を与えます。

numpy を使用する場合:

x = np.arange(20)
N = 15
x[x>15][0]

16 を与えます。

特定の問題について、簡単な実装を探していた場合は、それに戻りましょう。

于 2012-12-02T13:46:15.137 に答える
0 
def modBinarySearch(arr,x):
    l=len(arr)
    mid=l/2
    if arr[mid] >= x and arr[mid-1] < x:
        return arr[mid]
    elif arr[mid]>x and arr[mid-1]>x:
        num = modBinarySearch(arr[0:mid],x)
    else:
        num = modBinarySearch(arr[mid:l],x)
    return num

N=int(raw_input('Enter a number: '))
arr=[1, 2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383]
print modBinarySearch(arr,N)
于 2015-04-07T19:36:28.327 に答える