0

那么问题如下：

首先，我正在使用 Python 进行编码。我有一个排序的自然数“givenY”的数组（Numpy 数组，但如果它可以帮助我将其更改为列表）。我想找到并指向位于两个指定值之间的第一个和最后一个a=Y[i]元素b=Y[i+1]。我编写了代码，但我相信我是以最糟糕的方式之一编写的，我不确定代码在时间上是否有效。因此，如果我能得到评论或建议从头开始编写它，我会很高兴。Y[i]重要的是有很多例外情况，在and之间没有 givenY 的元素Y[i+1]（通过分配-1给 start 来处理）。我的代码是：

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;

一些简单的输入和输出：

对于给定的 Y=[2,5,8,10]：

  • a=3,b=4，输出：值之间没有。（在我的代码中开始=-1）
  • a=2,b=5，输出：值之间没有。（在我的代码中开始=-1）
  • a=2,b=9 输出：开始=1,结束=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, 输出：值之间没有。（在我的代码中 start=-1）
  • a=5,b=5, 输出：值之间没有。（在我的代码中 start=-1）

在我目前工作的情况下，b 总是大于 a。

非常感谢。

4

2 回答 2

3

我不太明白返回的索引。例如，如果givenY是和空列表，两者都start将end是-1。此外，您发布的代码不会处理列表中的重复值。

bisect您可以使用该模块代替手动编码的二进制搜索。有关详细信息，请参阅 API 文档：

  1. 蟒蛇 3.3 - 8.6。bisect - 数组二等分算法
  2. 蟒蛇 2.7.3 - 8.5。bisect - 数组二等分算法

下面是一个返回的实现，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()。保留原始代码，因为恕我直言，在使用 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()
于 2013-02-26T20:14:53.997 回答
0

首先对列表进行排序，然后进行线性搜索。

去掉分号，它们不需要也不需要...

于 2013-02-26T17:16:48.200 回答