二分查找的變形
傳統的二分查找
數組時有序的，要么升序要么降序，這里不考慮重復元素出現的情況。
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 閱讀(179)
評論(0) 編輯 收藏 引用