Search for before and after values ​​in a long sorted list

Question

What will be the fastest way to search for a number (for example, 12.31) in a long sorted list and get the values ​​one before and after my “search” value when the exact value is not found (for example, 11.12 and 12.03 in the list below)?
Thank you very much in advance.

long_list = [10.11, 11.12, 13.03, 14.2 .. 12345.67]

Answer 1

The fastest way is probably to use the built-in support in python. Here I am thinking of a bisect module. Below I use a dictionary to quickly check O (1) if the value is in the list; if not, it is bisectused to find values ​​smaller and larger than the desired value.

#!/usr/bin/env python

import bisect

def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect.bisect_left(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bisect.bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

# First create a test-list (49996 items)
i=1.0
R=[1.0]
D={}
while i < 10000:
    i+=0.2
    i=round(i,2)
    D[i]=True
    R.append(i)

# Locate a value, in this case 100.3 which is not in the list
x=100.3
if D.has_key(x):
    print "found", x
else:
    print find_lt(R, x)
    print find_gt(R, x)

x=100.3:

100.2
100.4

Answer 2

( AKA) , , . , 0 , , , . , .

. .

Answer 3

If your list is sorted as in your example, I assume that binary search will be the fastest.

Answer 4

li = [10.11, 11.12, 13.03, 14.2, 15.6, 15.8, 17.9, 12345.67]

def searsh(x,li):
    itli = iter(li)
    a = itli.next()
    if a==x:
        return a
    else:
        while True:
            b = itli.next()
            if b==x:
                return b
            elif a<x<b:
                return (a,b)
            a = itli.next()
            if a==x:
                return a
            elif b<x<a:
                return (b,a)


print searsh(13.5,li)
print searsh(10.11,li)
print searsh(50.3,li)
print searsh(12345.67,li)

result

(13.03, 14.2)
10.11
(17.9, 12345.67)
12345.67

also:

def searsh(x,li):
    a = li[0]
    if a==x:
        return a
    else:
        j = 0
        while True:
            j += 1
            b = li[j]
            if b==x:
                return b
            elif a<x<b:
                return (a,b)
            j += 1
            a = li[j]
            if a==x:
                return a
            elif b<x<a:
                return (b,a)