Who's Studio.

hihoCoder#1133 - 二分·二分查找之k小数

Word count: 296Reading time: 1 min
2016/05/17

题目

给定一个数组，求排好序的该数组中第k小的数。
具体描述请见hihoCoder。

解题思路

二分查找。采用类似快排里split的思想，每次计算数组第一个元素在排好序的该数组中的位置，并且判断该位置与k的大小关系，进行二分。

时间复杂度

类似快排，平均情况下时间复杂度为NlogN。最坏情况是N2。

代码

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
using namespace std;

int split(int* array, int start, int end) {
	int i = start;
	int x = array[start];
	for (int j = i + 1; j <= end; j++) {
		if (array[j] < x) {
			i++;
			int tmp = array[i];
			array[i] = array[j];
			array[j] = tmp;
		}
	}
	array[start] = array[i];
	array[i] = x;

	return i;
}

int search(int* array, int start, int end, int k) {
	int mid = split(array, start, end);
	if (k == mid)
		return array[mid];
	else if (k < mid)
		return search(array, start, mid - 1, k);
	else
		return search(array, mid + 1, end, k);
}

int find(int* array, int N, int k) {
	if (k > N)
		return -1;

	return search(array, 0, N - 1, k - 1);
}

int main() {
	int N = 0, k = 0;
	cin >> N >> k;
	int* array = new int[N];
	for (int i = 0; i < N; i++)
		cin >> array[i];

	cout << find(array, N, k) << endl;

	return 0;
}

Author：Who Watson

Link：https://wangshenghu.github.io/2016/05/17/2016-05-17-hihocoder-binary-search-kth/

Publish date：May 17th 2016, 4:13:20 pm

Update date：December 4th 2022, 5:09:25 pm

License：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 题目
  2. 2. 解题思路
  3. 3. 时间复杂度
  4. 4. 代码
Total : 56
2022
2016
test
笔记 算法 hihoCoder 实习经历 项目