本文實例講述了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++算法設計的學習有所幫助。
新聞熱點
疑難解答
圖片精選
