查找算法总结

二分查找

1. 适用场景
适用于对排好序的序列的指定值进行查找
2. 复杂度
O(logN)
3. 代码

/*cpp*/
int binarySearch(int[] a, int key)
 {
 	 int a_len = sizeof(a)/sizeof(a[0]);
	 int lo = 0, hi = a_len - 1;
	 while (lo <= hi)
	 {
	 	int mid = lo + (hi - lo) / 2;
	 	if (key < a[mid]) hi = mid - 1;
	 	else if (key > a[mid]) lo = mid + 1;
	 	else return mid;
	 }
 	return -1;
 }

快速查找

1. 适用场景
找一个混合序列中的第(/或者前)k大（/或者小）的值
2. 复杂度
O(N)
3. 代码