C++完成扭轉數組的二分查找。本站提示廣大學習愛好者:(C++完成扭轉數組的二分查找)文章只能為提供參考,不一定能成為您想要的結果。以下是C++完成扭轉數組的二分查找正文
本文實例講述了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++算法設計的進修有所贊助。