binary, bisect search

Posted on
Words count in article: 250 words | Reading time ≈ 2 mins 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def binary_search_recursion(list1, val, low, high):
	if high < low:
		return None 
	mid = (low + high) // 2
	if list1[mid]>val:
		return binary_search_recursion(list1, val, low, mid-1)
	elif list1[mid] < val:
		return binary_search_recursion(list1, val, mid+1, high)
	else:
		return mid 

## faster than recursion
def binary_search_iterative(list1, val):
	l, r = 0, len(list1)-1
	while l <= r:
		mid = (l+r) // 2
		if list1[mid] < val:
			l = mid + 1
		elif list1[mid] > val:
			h = mid - 1
		else:
			return mid 
	return 

## test
import random
import timeit
list1 = [random.randint(0, 100000) for _ in range(10000)]
list1.sort()

def test_recursion():
	binary_search_recursion(list1, 888, 0, len(list1)-1)

t1 = timeit.Timer('test_recursion', setup='from __main__ import test_recursion')

Much faster way

1
2
3
4
5
6
7
8
9
10
import bisect
list1 = []
for i in range(1000):
	r = random.randint(1, 100)

	## find index for r to insert, same as bisect_right
	pos = bisect.bisect(list1, r)

	## actual insert, same as insort_right
	bisect.insort(list1, r)

numpy searchsorted

Used in numpy array

1
2
3
4
5
6
7
8
data = np.arrange(0, 1000)
np.searchsorted(data, 888)

## insert to the right, add side parameter
np.searchsorted(data, 3, side='right')

## search multiple value
np.searchsorted([1,2,3,4,5], [-10, 10, 2, 3])