本文实例讲述了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++算法设计的学习有所帮助。
如果您对该产品感兴趣，请填写办理（客服微信：xiaoxiongyidong）
发表评论
◎欢迎参与讨论，请在这里发表您的看法、交流您的观点。