搜索算法总结

对最近学习的基础算法做一些总结，并举出一些相应的例子，仅此作为记录。

减治法(Decrease-and-Conquer)

减常因子

二分查找（Binary Search）：

function BinSearch(A[0..n − 1], k)
	lo ← 0
	hi ← n − 1
	while lo ≤ hi do
		m ← ⌊(lo + hi)/2⌋
		if A[m] = k then
			return m
		if A[m] > k then
			hi ← m − 1
		else
			lo ← m + 1
		return −1

Lomuto区分（Lomuto Partitioning）与 找出的第k小的元素的快速选择：
要注意的是k - 1 - s - lo意味着从s+1数起的第k0小元素：

function LomutoPartition(A[lo..hi])
	p ← A[lo]
	s ← lo
	for i ← lo + 1 to hi do//利用i和p之间的差去换
		if A[i] < p then
			s ← s + 1
		swap(A[s], A[i])
		swap(A[lo], A[s])
	return s

function QuickSelect(A[.], lo, hi, k)
	s ← LomutoPartition(A, lo, hi)
	if s − lo = k − 1 then 
		return A[s]
	else
		if s − lo > k − 1 then
			QuickSelect(A, lo,s − 1, k)
		else
			QuickSelect(A,s + 1, hi,(k − 1) − (s − lo))