2013-02-26 68 views
0

那麼問題如下:查找位於兩個值之間的數組的元素

首先,我使用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。

非常感謝。

+1

請提供樣本輸入和輸出。 – ATOzTOA 2013-02-26 17:18:03

+1

什麼是'givenY',這是一個列表嗎? – ATOzTOA 2013-02-26 17:25:59

回答

3

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

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

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

下面是返回startend這樣一個實現以下屬性持有:

  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() 
+0

非常感謝您的時間,但這段代碼不起作用: 對於givenY = [1,3,5,7]它應該返回(3,3),但它返回 (3,4)甚至超過了界限。正如我前面提到的,當a和b之間沒有給定的Y值供以後使用時,我設置start = -1。 – Cupitor 2013-02-26 20:51:59

+0

在這種情況下,Y [i]和Y [i + 1]的值是多少?請閱讀這篇文章,因爲我已經明確了什麼是返回值。特別是,我聲明數組[開始:結束]將返回邊界之間的值。在這個特殊情況下,4不在界限之外,'[1,3,5,7] [3:4]'將返回'[7]',因爲上限指向不包含的第一個元素(類似於C++中的迭代器)。如果你可以指定在不同情況下返回的內容,我將修改代碼來處理這個問題。 – TAS 2013-02-26 21:36:01

+0

它們是整數值,但這並不重要,因爲我說你可以用a和b來代替它們。非常感謝,但我想結束指向間隔中的最後一個元素!我已經在我的文章中寫過很多輸入和輸出(在帖子結尾處) – Cupitor 2013-02-26 22:06:59

1

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

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

+0

感謝提醒列表已排序。因此使用二分搜索似乎比線性搜索更合乎邏輯。 我更喜歡分號,它讓我想起了C和Java,但感謝提及! – Cupitor 2013-02-26 17:17:29

+0

嗯python不是C或Java ... – ATOzTOA 2013-02-26 17:21:20

+1

線性搜索不會比二分查找慢嗎? – senderle 2013-02-26 17:21:39

相關問題