 ## Finding elements of a table between two values | |
[ 所属分类 开发（python） | 发布者 店小二03 | 时间 2019 | 作者 红领巾 ] 0人收藏点击收藏

Well the question is as follows:

First of all I am coding in python. I have an array(Numpy array but if it could be any of help I can change it to a list) of sorted natural numbers, "givenY". I want to find and point to the first and last element in which fall between two specified values a=Y[i] and b=Y[i+1] . I wrote the code but I believe I did in one of the nastiest possible ways and I am not sure if the code is temporally efficient. So I would be happy if I could get comments or get a suggestion to write it from the scratch. The important things is there are many exceptional situations when there is no element of givenY between Y[i] and Y[i+1] (which are handled by assigning -1 to start). My code is: startRes=binSearch(givenY,Y[i]); endRes=binSearch(givenY,Y[i+1]); start=startRes end=endRes; if(givenY.size==0 or (givenY.size>0 and givenY[start]<=Y[i])): start=startRes+1; if(endRes): end=endRes-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 if startRes: start=start+1; end=endRes-1;

And this is the implementation of 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;

Some simple input and outputs:

For the givenY=[2,5,8,10]: a=3,b=4, output: no in between values.(start=-1 in my code) a=2,b=5, output: no in between values.(start=-1 in my code) a=2,b=9 output: start=1,end=2 a=1,b=10,output: start=0,end=2 a=1,b=11,output: start=0,end=3 a=11,b=12, output: no in between values.(start=-1 in my code) a=0,b=2, output: no in between values.(start=-1 in my code) a=3,b=3, output: no in between values.(start=-1 in my code) a=5,b=5, output: no in between values.(start=-1 in my code)

In the case I am currently working, b is always greater than a.

Thanks a lot.

I don't quite understand the indices returned. For example, if givenY is and empty list, both start and end will be -1. Also, the code you posted will not handle duplicate values in the list.

Instead of hand-coded binary search you can use the bisect module. For details see the API documentation:

Python 3.3 - 8.6. bisect ― Array bisection algorithm Python 2.7.3 - 8.5. bisect ― Array bisection algorithm

Below is an implementation that returns start and end so that the following properties hold:

end-start list[start:end] end-start start==end

Code:

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, self.Y) ) def test_both_endpoints_inside_list(self): self.assertEqual( (1, 2), find_range(self.givenY, self.Y, self.Y)) self.assertEqual( , self.givenY[1:2]) def test_2(self): self.assertEqual( (3, 7), find_range(self.givenY, self.Y, self.Y) ) 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, self.Y) ) self.assertEqual( , self.givenY[8:9]) if __name__=="__main__": unittest.main()

NOTE: The returned start and end positions should easily be adjusted to your current values if needed, just make sure that it is consistent.

EDIT

Below is code that returns the values requested, as far as I can understand from the samples given. The logic is described in the find_range() docstring. The original code is kept as it IMHO feels more natural when programming in 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, self.Y) ) def test_both_endpoints_inside_list(self): self.assertEqual( (1, 1), find_range(self.givenY, self.Y, self.Y)) def test_2(self): self.assertEqual( (3, 6), find_range(self.givenY, self.Y, self.Y) ) def test_no_values_larger_or_equal_to_upper_limit(self): self.assertEqual( (8, 8), find_range(self.givenY, self.Y, self.Y) ) 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()

1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责；
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性，不作出任何保证或承若；
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。 技术大类 | 开发（python） | 评论(0) | 阅读(215)