Searching

Algorithm, C++, Search, leetcode

常见的查找算法

二分查找

Binary Search
Runtime: O(logn)O(logn). Memory:O(1)O(1). 只适用于有序表、顺序存储结构。

二分查找算法解释

  • 先确定待查记录所在的范围，然后逐步减半缩小范围知道找到或找不到该记录为止。

代码

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
#include <iostream>
int binary_search(int* num_array, int n, int target)
{
	if (!num_array || n < 1) return -1;
	int low(0), high(n-1);
	while (low <= high)
	{
		int mid((low + high)/2);
		if (num_array[mid] == target) {return mid;}	// 找到
		else if (num_array[mid] < target) {low = mid + 1;}	// 在右半区间
		else {high = mid - 1;}	// 在左半区间
	}
	return -1;	// 没找到
}
int main()
{
	int A[1] = {1};
	int B[2] = {1, 2};
	int C[10] = {-1, 0, 5, 6, 7, 10, 500, 654, 999, 1000};
	std::cout<<binary_search(NULL, 0, 10)<<std::endl;
	std::cout<<binary_search(A, 1, 1)<<std::endl;
	std::cout<<binary_search(A, 1, 10)<<std::endl;
	std::cout<<binary_search(B, 2, 2)<<std::endl;
	std::cout<<binary_search(B, 2, 10)<<std::endl;
	std::cout<<binary_search(C, 10, 999)<<std::endl;
	std::cout<<binary_search(C, 10, -5)<<std::endl;
	system("Pause");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int binary_search(const vector<int>& array, int num)
{
	if (array.empty()) return -1;
	int left(0), right(array.size());
	while (left < right)
	{
		int mid = left + (right - left) / 2;
		if (array[mid] < num)
		{
			left = mid + 1;
		}else if (array[mid] > num)
		{
			right = mid;
		}else
		{
			return mid;
		}
	}
	return -1;
}

Lower Bound

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& val)
{
	ForwardIterator it;
	iterator_traits<ForwardIterator>::difference_type count, step;
	count = distance(first, last);
	while (count > 0)
	{
		it = first; step = count / 2; advance(it, step);
		if (*it < val) {                 // or: if (comp(*it,val)), for version (2)
			first = ++it;
			count -= step + 1;
		}
		else count = step;
	}
	return first;
}

Upper Bound

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <class ForwardIterator, class T>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& val)
{
	ForwardIterator it;
	iterator_traits<ForwardIterator>::difference_type count, step;
	count = std::distance(first, last);
	while (count > 0)
	{
		it = first; step = count / 2; std::advance(it, step);
		if (!(val < *it))                 // or: if (!comp(val,*it)), for version (2)
		{
			first = ++it; count -= step + 1;
		}
		else count = step;
	}
	return first;
}

二叉查找树

关于二叉查找树详细见这里。

哈希表

关于哈希表/散列表的一些讲解看这里。

leetcode相关题目

Search for a Range
Search Insert Position
Search a 2D Matrix
Search a 2D Matrix II
Kth Smallest Element in a Sorted Matrix

[1] Cracking the Code Interview
[2] leetcode