本文实例讲述了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; } }
希望本文所述对大家C++算法设计的学习有所帮助。
【C++实现旋转数组的二分查找】相关文章：