《编程珠玑》学习笔记

书是买了好久，一直没心情，到今天才拿起来看，算法使用python实现。

位图排序

import random
# 产生一组随机数
unsorted = [random.randint(1, 19) for i in range(7)]

print(unsorted)
# 初始化一个向量组
bits = [0] * 20
# 储存排序后的结果
hsorted = []
# 对号入座
for i in unsorted:
	bits[i] = 1
for n, m in enumerate(bits):
	if m == 1:
		hsorted.append(n)

print(hsorted)

二分法查找

lis = [0,1,2,3,4,5,6,7,8]

search = 7.5

def binarySearch(lis, search):
	low = 0
	high = len(lis) - 1
	while low <= high:
		#mid = (low + high) // 2
		mid = (low + high) >> 1
		if search < lis[mid]:
			high = mid - 1
		elif search > lis[mid]:
			low = mid + 1
		elif search == lis[mid]:
			return mid
	if low > len(lis) - 1 or high < 0:
		return -1
	return (high, low)

print(binarySearch(lis, search))