通过本文主要向大家介绍了c++数组怎么用,c++数组教程,c++动态二维数组,c++动态数组,c++二维数组等相关知识,希望对您有所帮助,也希望大家支持linkedu.com www.linkedu.com
本文实例讲述了C++实现旋转数组的二分查找方法，分享给大家供大家参考。具体方法如下：
题目要求：
旋转数组，如{3, 4, 5, 1, 2}是{1, 2, 3, 4, 5}的一个旋转，要求利用二分查找查找里面的数。
这是一道很有意思的题目，容易考虑不周全。这里给出如下解决方法：
#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;
}
}
</div>
希望本文所述对大家C++算法设计的学习有所帮助。
</div>