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++算法设计的学习有所帮助。

赞 (0)

相关推荐

  • C++二分查找算法实例

    本文实例为大家分享C++二分查找算法,通过改变边界位置来进行查找的方法,代码如下: #include <iostream> using namespace std; int search(int *p,int length,int key); int search1(int *p,int length,int key); int main() { cout << "Hello world!" << endl; int a[] = {1,2,3,4,5

  • C++二分查找(折半查找)算法实例详解

    本文实例讲述了C++二分查找(折半查找)算法.分享给大家供大家参考,具体如下: 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好:其缺点是要求待查表为有序表,且插入删除困难. 因此,折半查找方法适用于不经常变动而查找频繁的有序列表. 二分查找思想 首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功: 否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表. 重复

  • C++二分查找在搜索引擎多文档求交的应用分析

    本文实例讲述了C++二分查找在搜索引擎多文档求交的应用.分享给大家供大家参考.具体如下: int search2(int array[], int n, int v) { int left, right, middle; left = 0, right = n - 1; while (left <= right) { middle = (left + right) / 2; if (array[middle] > v) { right = middle - 1; } else if (arra

  • C++ 中二分查找递归非递归实现并分析

    C++ 中二分查找递归非递归实现并分析

    C++ 中二分查找递归非递归实现并分析 二分查找在有序数列的查找过程中算法复杂度低,并且效率很高.因此较为受我们追捧.其实二分查找算法,是一个很经典的算法.但是呢,又容易写错.因为总是考虑不全边界问题. 用非递归简单分析一下,在编写过程中,如果编写的是以下的代码: #include<iostream> #include<assert.h> using namespace std; int binaty_search(int* arr, size_t n, int x) { asse

  • 二分查找算法在C/C++程序中的应用示例

    二分查找算法的思想很简单,<编程珠玑>中的描述: 在一个包含t的数组内,二分查找通过对范围的跟综来解决问题.开始时,范围就是整个数组.通过将范围中间的元素与t比较并丢弃一半范围,范围就被缩小.这个过程一直持续,直到在t被发现,或者那个能够包含t的范围已成为空.         Donald Knuth在他的<Sorting and Searching>一书中指出,尽管第一个二分查找算法早在1946年就被发表,但第一个没有bug的二分查找算法却是在12年后才被发表出来.其中常见的一个

  • 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

  • 详解Java数据结构和算法（有序数组和二分查找）

    一.概述 有序数组中常常用到二分查找,能提高查找的速度.今天,我们用顺序查找和二分查找实现数组的增删改查. 二.有序数组的优缺点 优点:查找速度比无序数组快多了 缺点:插入时要按排序方式把后面的数据进行移动 三.有序数组和无序数组共同优缺点 删除数据时必须把后面的数据向前移动来填补删除项的漏洞 四.代码实现 public class OrderArray { private int nElemes; //记录数组长度 private long[] a; /** * 构造函数里面初始化数组 赋值默

  • 使用PHP实现二分查找算法代码分享

    第一种方法: [二分查找要求]:1.必须采用顺序存储结构 2.必须按关键字大小有序排列. [优缺点]折半查找法的优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难.因此,折半查找方法适用于不经常变动而查找频繁的有序列表. [算法思想]首先,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功:否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表. 复制代码 代码如下: <?

  • 在MySQL中实现二分查找的详细教程

    给定一个升序排列的自然数数组,数组中包含重复数字,例如:[1,2,2,3,4,4,4,5,6,7,7].问题:给定任意自然数,对数组进行二分查找,返回数组正确的位置,给出函数实现.注:连续相同的数字,返回第一个匹配位置还是最后一个匹配位置,由函数传入参数决定. 我为什么会出这道题目? 二分查找在数据库内核实现中非常重要 在数据库的内核实现中,二分查找是一个非常重要的逻辑,几乎99%以上的SQL语句(所有索引上的范围扫描/等值查询/Unique查询等),都会使用到二分查找进行数据的定位. 考虑一个

  • Java实现二分查找的变种

    Java实现二分查找的变种

    本文实例为大家分享了Java实现二分查找的变种,供大家参考,具体内容如下 普通二分查找: 先回顾一下普通的二分查找 注意:二分查找有这样一个问题:当数组中数有重复时,比如 {3,3,3,3} 这个数组,二分查找3时,返回的是arr[1],也就是说二分查找并不会返回3第一次出现的位置0. public class BinarySearch { public static <T extends Comparable<? super T>> int search(T arr[], T v

  • 面试题:Java 实现查找旋转数组的最小数字

    在算法面试中,面试官总是喜欢围绕链表.排序.二叉树.二分查找来做文章,而大多数人都可以跟着专业的书籍来做到倒背如流.而面试官并不希望招收的是一位记忆功底很好,但不会活学活用的程序员.所以学会数学建模和分析问题,并用合理的算法或数据结构来解决问题相当重要. 面试题:打印出旋转数组的最小数字 题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转.输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素.例如数组 {3,4,5,1,2} 为数组 {1,2,3,4,5} 的一个旋转,该

  • JavaScript使用二分查找算法在数组中查找数据的方法

    本文实例讲述了JavaScript使用二分查找算法在数组中查找数据的方法.分享给大家供大家参考.具体分析如下: 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好:其缺点是要求待查表为有序表,且插入删除困难.因此,折半查找方法适用于不经常变动而查找频繁的有序列表.首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功:否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一

  • Python查找数组中数值和下标相等的元素示例【二分查找】

    本文实例讲述了Python查找数组中数值和下标相等的元素.分享给大家供大家参考,具体如下: 题目描述: 假设一个单调递增的数组中的每个元素都是整数并且是唯一的.请编程实现一个函数,找出数组中任意一个数值等于其下标的元素,例如在数组[-3,-1,1,3,5]中,3和他的下标相等. 采用二分查找:如果数组中的数字小于下标,由于下标是-1的递减数列,但是数组中的元素差值大于等于-1,因此左边的不可能等于下标.如果数组中的数字大于下标,同理,之后的数字肯定都大于下标,往左边查找. 算法示例: # -*-

  • C语言编程之初识数组线性查找和二分查找

    C语言编程之初识数组线性查找和二分查找

    目录 线性查找 二分查找 先来了解一下什么是查找, 额,好吧,这没什么可了解的, 就是查找数组中的某个元素的位置或是否存在. 就这,没了.直接了解查找算法吧. 线性查找 线性查找与二分查找有些差别. 数组内元素可以是混乱无序的,即没有按顺序储存.这方法很简单,就是从首元素开始,依此向后查找,比较.仅此而已.运用循环,依次对比. 看代码吧. #include <stdio.h> int main(void) { int arr[] = { 5,4,6,8,7,9,10,2,3,1 }; int

  • Java二分查找算法与数组处理的应用实例

    Java二分查找算法与数组处理的应用实例

    目录 1.特殊数组的特征值 题目描述 思路详解 代码与结果 2.在D天内送达包裹的能力 题目描述 思路详解 代码与结果 3.咒语和药水的成功对数 题目描述 思路详解 代码与结果 总结 1.特殊数组的特征值 题目描述 思路详解 看到本题,首先思考需要排序,然后查找,这里为了效率采用二分查找. 假设定义x=(left+riht)/ 2,每次查找到nums中第一个大于等于X的元素下标,判断大于等于X的个数与X的关系,进行分情况修改左右边界. 代码与结果 class Solution { public

随机推荐