|
c int search_desc(int a[], int len, int v) {
int begin = 0, end = len;
while (begin < end) {
int mid = (begin + end) / 2;
if (a[mid] == v)
return mid;
if (a[begin] > a[mid]) {
// 左边有序 [begin, mid]
if (a[begin] >= v && v > a[mid])
return bsearch_desc(a, begin, mid, v);
// 右边无序, 继续循环
begin = mid + 1;
} else if (a[begin] < a[mid]) {
// 右边有序 [mid, end)
if (a[mid] > v && v >= a[end - 1])
return bsearch_desc(a, mid + 1, end, v);
// 左边无须, 继续循环
end = mid;
} else {
++begin;
}
}
// 没有找到
return -1;
}
//
// 题目:
// 一类有序数组旋转查值问题.
// 例如:
// 有序数组 [ 1, 2, 3, 5, 5, 7, 7, 8, 9 ] 旋转后为 [ 5, 7, 7, 8, 9, 1, 2, 3, 5 ]
// 如何从中找出一个值索引, not found return -1.
int
search_upgrade(int a[], int len, int v) {
int state, i, s[3];
if (a == NULL || len <= 0)
return -1;
// 默认 desc 降序
if (len == 1) {
if (a[0] == v)
return 0;
return -1;
}
if (len == 2) {
if (a[0] == v)
return 0;
if (a[1] == v)
return 1;
return -1;
}
// 摘取不重复的3个内容
s[0] = a[0];
// 开始找 s[1]
for (i = 1; i < len; ++i) {
if (a[i] == s[0])
continue;
break;
}
// 所有值都一样, 走默认降序
if (i >= len) {
if (s[0] == v)
return 0;
return -1;
}
s[1] = a[state = i];
// 开始找 s[2]
while (i < len) {
if (a[i] == s[0] || a[i] == s[1]) {
++i;
continue;
}
break;
}
// 只有两个不一样的值, 走默认降序
if (i >= len) {
if (s[0] == v)
return 0;
if (s[1] == v)
return state;
return -1;
}
s[2] = a[i];
state = 0;
state += s[0] > s[1] ? 1 : -1;
state += s[1] > s[2] ? 1 : -1;
state += s[2] > s[0] ? 1 : -1;
// desc 降序, 旋转
if (state >= 0)
return search_desc(a, len, v);
// asc 升序, 旋转
return search_asc(a, len, v);
}
不同分支不同代码, 针对性强. 代码最坏的情况是 O(n).
这里不妨来个测试演示
#include <stdio.h>
#include <stdlib.h>
#define LEN(a) (sizeof(a)/sizeof(*a))
// print - 数据内容打印
#define INT_BR (15)
static void print(int a[], int len) {
int i = 0;
while (i < len) {
printf(" %d", a[i]);
if (!(++i % INT_BR))
putchar('\n');
}
if (i % INT_BR)
putchar('\n');
}
int search_upgrade(int a[], int len, int v);
// sort - 旋转查找
int main(int argc, char * argv[]) {
int i, v;
int a[] = { 5, 7, 7, 8, 9, 1, 2, 3, 5 };
print(a, LEN(a));
// 开始测试
v = 8;
i = search_upgrade(a, LEN(a), v);
printf("%d -> %d\n", v, i);
v = 5;
i = search_upgrade(a, LEN(a), v);
printf("%d -> %d\n", v, i);
v = 6;
i = search_upgrade(a, LEN(a), v);
printf("%d -> %d\n", v, i);
v = 7;
i = search_upgrade(a, LEN(a), v);
printf("%d -> %d\n", v, i);
v = 4;
i = search_upgrade(a, LEN(a), v);
printf("%d -> %d\n", v, i);
int b[] = { 7, 6, 5, 3, 3, 2, 1, 9, 9, 8, 8, 7, 7 };
print(b, LEN(b));
// 开始测试
v = 8;
i = search_upgrade(b, LEN(b), v);
printf("%d -> %d\n", v, i);
v = 5;
i = search_upgrade(b, LEN(b), v);
printf("%d -> %d\n", v, i);
v = 6;
i = search_upgrade(b, LEN(b), v);
printf("%d -> %d\n", v, i);
v = 7;
i = search_upgrade(b, LEN(b), v);
printf("%d -> %d\n", v, i);
v = 4;
i = search_upgrade(b, LEN(b), v);
printf("%d -> %d\n", v, i);
return EXIT_SUCCESS;
}
当前输出结果如下
$ gcc -g -Wall sort.c ; ./a.out
5 7 7 8 9 1 2 3 5
8 -> 3
5 -> 0
6 -> -1
7 -> 2
4 -> -1
7 6 5 3 3 2 1 9 9 8 8 7 7
8 -> 10
5 -> 2
6 -> 1
7 -> 0
4 -> -1
后记 - 感谢
错误是难免的 ~ 欢迎指正 : )
小桥 - |