查找位於兩個值之間的數組的元素

Question

那麼問題如下：

首先，我使用Python進行編碼。 我有一個數組（numpy數組，但如果它可以是任何幫助，我可以將它更改爲列表）的排序自然數，「givenY」。我想找到並指向第一個也是最後一個元素，它落在兩個指定值a=Y[i]和b=Y[i+1]之間。我編寫了代碼，但我相信我以最糟糕的一種方式做了，而且我不確定代碼是否在時間上有效。所以我會很高興，如果我能得到意見或建議從頭開始寫。重要的是，在Y[i]和Y[i+1]（它們通過分配-1開始處理）之間沒有給定Y的元素時，存在許多特殊情況。我的代碼是：

startRes=binSearch(givenY,Y[i]); 
endRes=binSearch(givenY,Y[i+1]);   
start=startRes[1] 
end=endRes[1];   
if(givenY.size==0 or (givenY.size>0 and givenY[start]<=Y[i])): 
    start=startRes[1]+1; 
if(endRes[0]): 
    end=endRes[1]-1; 
if end<start or (givenY.size>0 and (givenY[end]>Y[i+1] or givenY[start]>=Y[i+1])) or givenY[end]<=Y[i]: 
    start=-1; 

startRes=binSearch(givenY,a); 
endRes=binSearch(givenY,b);   
start=startRes[1] 
if startRes[0]: 
    start=start+1; 
end=endRes[1]-1;   

這是BINSEARCH執行：

def binSearch(arr,element): 
left=0 
right=arr.size; 
mid=(left+right)/2 
while left<right: 
    mid=(left+right)/2 
    if(arr[mid]<element): 
     left=mid+1; 
    elif (arr[mid]>element): 
     right=mid; 
    else: 
     return True,mid; 
return False,left; 

一些簡單的輸入和輸出：

對於givenY = [2,5,8,10]：

• A = 3，B = 4，輸出：無在值之間的（起始= -1在我的代碼）
• 一個= 2，b = 5，輸出：在這兩個值之間沒有數值（在我的代碼中start = -1）
• a = 2，b = 9輸出：start = 1，end = 2
• a = 1，b = 10，輸出：開始= 0，結束= 2
• a = 1，b = 11，輸出：開始= 0，結束= 3
• a = 11，b = 12，輸出：開始= -1在我的代碼）
• a = 0，b = 2，輸出：在這兩個值之間沒有（起始= -1）
• a = 3，b = 3，輸出：代碼）
• A = 5，b = 5，輸出：無在值之間的（起始= -1在我的代碼）

在我目前的工作的情況下，b爲總是大於a。

非常感謝。

Answer 1

我不太明白的指標恢復。例如，如果givenY是空列表，則start和end將爲-1。此外，您發佈的代碼不會處理列表中的重複值。

您可以使用bisect模塊代替手動編碼的二進制搜索。有關詳情請參閱API文檔：

1. Python 3.3 - 8.6. bisect — Array bisection algorithm
2. Python 2.7.3 - 8.5. bisect — Array bisection algorithm

下面是返回start和end這樣一個實現以下屬性持有：

1. end-start等於號在給定邊界之間的元素。
2. list[start:end]返回包含給定邊界之間所有值的切片。
3. end-start等於找到的元素數
4. 當沒有找到值時start==end。

代碼：

import unittest 

from bisect import bisect_left, bisect_right 


def find_range(array, a, b): 
    start = bisect_right(array,a) 
    end = bisect_left(array,b) 
    return (start, end) 


class TestCase(unittest.TestCase): 
    Y = [1, 3, 5, 10, 15] 
    givenY = [3, 4, 5, 6, 7, 8, 9, 10, 11] 

    def test_empty_array(self): 
     self.assertEqual((0, 0), find_range([], 1, 2)) 

    def test_all_values_larger(self): 
     self.assertEqual((0, 0), find_range([4,5,6], 1, 3)) 

    def test_all_values_larger_or_equal(self): 
     self.assertEqual((0, 0), find_range(self.givenY, self.Y[0], self.Y[1])) 

    def test_both_endpoints_inside_list(self): 
     self.assertEqual((1, 2), find_range(self.givenY, self.Y[1], self.Y[2])) 
     self.assertEqual([4], self.givenY[1:2]) 

    def test_2(self): 
     self.assertEqual((3, 7), find_range(self.givenY, self.Y[2], self.Y[3])) 
     self.assertEqual([6, 7, 8, 9], self.givenY[3:7]) 

    def test_no_values_larger_or_equal_to_upper_limit(self): 
     self.assertEqual((8, 9), find_range(self.givenY, self.Y[3], self.Y[4])) 
     self.assertEqual([11], self.givenY[8:9]) 


if __name__=="__main__": 
    unittest.main() 

注：返回的開始和結束位置應該很容易地調整到當前的值，如果需要的話，只是確保它是一致的。

編輯

下面是代碼，返回要求，只要我可以從給定的樣本瞭解值。邏輯在find_range()文檔字符串中描述。原始代碼保存爲IMHO在Python編程時感覺更自然。

import unittest 

from bisect import bisect_left, bisect_right 


def find_range(array, a, b): 
    """Find elements that are greater than a and less than b. 
    Returns a tuple (start,end) where array[start] is the first 
    value and array[end] is the last value. 
    If no value is found, returns start=end=-1. 
    """ 
    start = bisect_right(array,a) 
    end = bisect_left(array,b) 
    if start==end: 
     return (-1,-1) 
    else: 
     return (start, end-1) 


class TestCase(unittest.TestCase): 
    Y = [1, 3, 5, 10, 15] 
    givenY = [3, 4, 5, 6, 7, 8, 9, 10, 11] 

    def test_empty_array(self): 
     self.assertEqual((-1, -1), find_range([], 1, 2)) 

    def test_all_values_larger(self): 
     self.assertEqual((-1, -1), find_range([4,5,6], 1, 3)) 

    def test_all_values_larger_or_equal(self): 
     self.assertEqual((-1, -1), find_range(self.givenY, self.Y[0], self.Y[1])) 

    def test_both_endpoints_inside_list(self): 
     self.assertEqual((1, 1), find_range(self.givenY, self.Y[1], self.Y[2])) 

    def test_2(self): 
     self.assertEqual((3, 6), find_range(self.givenY, self.Y[2], self.Y[3])) 

    def test_no_values_larger_or_equal_to_upper_limit(self): 
     self.assertEqual((8, 8), find_range(self.givenY, self.Y[3], self.Y[4])) 

    def test_sample(self): 
     self.assertEqual((3,3), find_range([1,3,5,7], 5, 8) ) 
     self.assertEqual((3,3), find_range([1,3,5,7], 6, 8) ) 


if __name__=="__main__": 
    unittest.main() 

Answer 2

首先對列表進行排序，然後進行線性搜索。

刪除分號，它們並不需要和不需要......