二分查找的变形
传统的二分查找
数组时有序的，要么升序要么降序，这里不考虑重复元素出现的情况。
int foo(int a[], int n, int item)
{
int left = 0, right = n - 1;
int middle = 0;
while (left <= right)
{
middle = (left + right) / 2;
if (item > a[middle])
{
left = middle + 1;
}
else if (item < a[middle])
{
right = middle - 1;
}
else
{
return middle;
}
}
return -1;
}
二分查找的变形
给定一个数组 int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
如果对该数组调整为
{6, 7, 8, 9, 10, 1, 2, 3, 4, 5}
调整后即是两个连续有序序列，只不过整体不有序
还是用二分策略，但是具体细节需要改进
整体结构还是一样的
具体补充的是当待查找元素与中间元素不相等时，
如果小于，还要检测 item 与 a[left] 的大小关系
如果大于，还要检测 item 与 a[right] 的大小关系
int bar(int a[], int n, int item)
{
int left = 0, right = n - 1;
int middle = 0;
while (left <= right)
{
middle = (left + right) / 2;
if (item < a[middle])
{
if (a[left] < item)
{
right = middle - 1;
}
else if (a[left] > item)
{
left = middle + 1;
}
else
{
return left;
}
// right = middle - 1;
}
else if (item > a[middle])
{
if (a[right] > item)
{
left = middle + 1;
}
else if (a[right] < item)
{
right = middle - 1;
}
else
{
return right;
}
}
else
{
return middle;
}
}
return -1;
}
1 #include <iostream>
2 using namespace std;
3
4 int foo(int a[], int n, int item)
5 {
6 int left = 0, right = n - 1;
7 int middle = 0;
8 while (left <= right)
9 {
10 middle = (left + right) / 2;
11 if (item > a[middle])
12 {
13 left = middle + 1;
14 }
15 else if (item < a[middle])
16 {
17 right = middle - 1;
18 }
19 else
20 {
21 return middle;
22
23 }
24 }
25 return -1;
26 }
27
28 int bar(int a[], int n, int item)
29 {
30 int left = 0, right = n - 1;
31 int middle = 0;
32 while (left <= right)
33 {
34 middle = (left + right) / 2;
35 if (item < a[middle])
36 {
37 if (a[left] < item)
38 {
39 right = middle - 1;
40 }
41 else if (a[left] > item)
42 {
43 left = middle + 1;
44 }
45 else
46 {
47 return left;
48 }
49 // right = middle - 1;
50 }
51 else if (item > a[middle])
52 {
53 if (a[right] > item)
54 {
55 left = middle + 1;
56 }
57 else if (a[right] < item)
58 {
59 right = middle - 1;
60 }
61 else
62 {
63 return right;
64 }
65 }
66 else
67 {
68 return middle;
69 }
70 }
71 return -1;
72 }
73
74 int main()
75 {
76 int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
77 cout << foo(a, sizeof (a) / sizeof (*a), 3) << endl;
78 int b[] = {6, 7, 8, 9, 10, 1, 2, 3, 4, 5};
79 cout << bar(b, sizeof (b) / sizeof (*b), 5) << endl;
80 return 0;
81 }
实现：
posted on 2011-10-29 00:04
unixfy 阅读(174)
评论(0) 编辑 收藏 引用