Who's Studio.

hihoCoder#1128 - 二分·二分查找

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

题目

给定一个数组，求一个数字K在排好序的该数组中哪个位置。
具体描述请见hihoCoder。

解题思路

二分查找。采用类似快排里split的思想，将K插入数组最后一个位置并运行一遍split函数找到K在排好序的该数组中的位置，然后只要检查在K右侧的数字里是否有等于K的数即可。

时间复杂度

split函数用时N，检查一遍用时N，整体时间复杂度为2N。

代码

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
#include <iostream>
using namespace std;

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

	return i;
}

int find(int* array, int N) {
	int mid = split(array, 0, N);
	for (int i = mid + 1; i <= N; i++)
		if (array[i] == array[mid])
			return mid + 1;

	return -1;
}

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

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

	return 0;
}

Author：Who Watson

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

Publish date：May 17th 2016, 4:01:15 pm

Update date：December 4th 2022, 5:11:43 pm

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

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