需要幫助解決二進制搜索

-1

我已經實現瞭解決這個問題所需的二進制搜索功能，但我不能返回正確的值，這將有助於我解決這個問題。這是我的代碼。

請幫我解決這個問題。

def BinarySearch(arr,low,high,search): 
    while(low<=high): 

     middle=(low+high)/2 
     int_mid=int(middle) 
     print(int_mid) 

     if arr[int_mid]==search: 
      return int_mid 
     elif arr[int_mid]>search: 
      low=int_mid+1 
     elif arr[int_mid]<search: 
      high=int_mid-1 


    return arr[int_mid] 


tc=int(input()) 

while(tc>0): 
    size=int(input()) 

    A=list(map(int,input().split())) 
    B=list(map(int,input().split())) 

    monkiness=[] 


    for i in range(len(A)): 
     for j in range(len(B)): 

      if (j>=i): 
       y=BinarySearch(B,0,len(B),B[j]) 
       z=BinarySearch(A,0,len(A),A[i]) 

      print(y,z) 
      if y>=z: 

       m=j-i 
       monkiness.append(m) 

if len(monkiness)==0: 
    print(0) 
else: 
    print(monkiness) 
    maxiumum=max(monkiness) 
    print(maxiumum) 
tc-=1

來源

2017-02-10 Dhruv Marwha

你的輸入和輸出是什麼？ –

它的值大約是1000+，所以它不適合here.Plus代碼無法打印輸出，因爲在線編譯器有時間限制，我的代碼超過了時間限制。超鏈接提到了問題以及樣本輸入和輸出。 –

二進制搜索不是最好的方法，但它可能可行。但是你需要自己創建一個測試用例 - 如果除了在一些隨機網站上不能測試代碼，可能會有比你猜測的更多或不同的問題。如果你要求其他人發現問題，提供一個失敗或者太慢的測試用例幾乎是必須的。 –

你不需要在這裏二進制搜索（「這裏」意味着你的代碼提供，而不是問題的解決）
即使你需要二進制搜索，BinarySearch對於非遞減排列，但你有不增加的數組。
目標是通過利用數組排序的事實，找到解決方案，運行時間少於N^2次。

來源

2017-02-10 10:28:56

我需要二進制搜索來找到解決方案，就好像我使用線性搜索，我得到的時間超過error.And我正在使用二進制搜索按降序order.All輸入按降序排列。 –

需要幫助解決二進制搜索

回答

相關問題