本文实例讲述了C++实现旋转数组的二分查找方法，分享给大家供大家参考。具体方法如下：
题目要求：
旋转数组，如{3, 4, 5, 1, 2}是{1, 2, 3, 4, 5}的一个旋转，要求利用二分查找查找里面的数。
这是一道很有意思的题目，容易考虑不周全。这里给出如下解决方法：
|
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
|
#include <iostream>using namespace std;int sequentialSearch(int *array, int size, int destValue){ int pos = -1; if (array == NULL || size <= 0) return pos; for (int i = 0; i < size; i++) { if (array[i] == destValue) { pos = i; break; } } return pos;}int normalBinarySearch(int *array, int leftPos, int rightPos, int destValue){ int destPos = -1; if (array == NULL || leftPos < 0 || rightPos < 0) { return destPos; } int left = leftPos; int right = rightPos; while (left <= right) { int mid = (right - left) / 2 + left; if (array[mid] == destValue) { destPos = mid; break; } else if (array[mid] < destValue) { left = mid + 1; } else { right = mid - 1; } } return destPos;}int rotateBinarySearch(int *array, int size, int destValue){ int destPos = -1; if (array == NULL || size <= 0) { return destPos; } int leftPos = 0; int rightPos = size - 1; while (leftPos <= rightPos) { if (array[leftPos] < array[rightPos]) { destPos = normalBinarySearch(array, leftPos, rightPos, destValue); break; } int midPos = (rightPos - leftPos) / 2 + leftPos; if (array[leftPos] == array[midPos] && array[midPos] == array[rightPos]) { destPos = sequentialSearch(array, size, destValue); break; } if (array[midPos] == destValue) { destPos = midPos; break; } if (array[midPos] >= array[leftPos]) { if (destValue >= array[leftPos]) { destPos = normalBinarySearch(array, leftPos, midPos - 1, destValue); break; } else { leftPos = midPos + 1; } } else { if (array[midPos] <= array[rightPos]) { destPos = normalBinarySearch(array, midPos + 1, rightPos, destValue); break; } else { rightPos = midPos - 1; } } } return destPos;}int main(){ //int array[] = {3, 4, 5, 1, 2}; //int array[] = {1, 2, 3, 4, 5}; //int array[] = {1, 0, 1, 1, 1}; //int array[] = {1, 1, 1, 0, 1}; //int array[] = {1}; //int array[] = {1, 2}; int array[] = {2, 1}; const int size = sizeof array / sizeof *array; for (int i = 0; i <= size; i++) { int pos = rotateBinarySearch(array, size, array[i]); cout << "find " << array[i] << " at: " << pos + 1 << endl; } for (int i = size; i >= 0; i--) { int pos = rotateBinarySearch(array, size, array[i]); cout << "find " << array[i] << " at: " << pos + 1 << endl; }} |
希望本文所述对大家C++算法设计的学习有所帮助。
