C++實現(xiàn)旋轉(zhuǎn)數(shù)組的二分查找

更新時間：2014年09月18日 09:24:14 投稿：shichen2014

這篇文章主要介紹了C++實現(xiàn)旋轉(zhuǎn)數(shù)組的二分查找方法,涉及數(shù)組的操作,有值得借鑒的技巧,需要的朋友可以參考下

本文實例講述了C++實現(xiàn)旋轉(zhuǎn)數(shù)組的二分查找方法，分享給大家供大家參考。具體方法如下：

題目要求：

旋轉(zhuǎn)數(shù)組，如{3, 4, 5, 1, 2}是{1, 2, 3, 4, 5}的一個旋轉(zhuǎn)，要求利用二分查找查找里面的數(shù)。

這是一道很有意思的題目，容易考慮不周全。這里給出如下解決方法：

#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++算法設(shè)計的學習有所幫助。

您可能感興趣的文章: