服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - C/C++ - C++实现旋转数组的二分查找

C++实现旋转数组的二分查找

2021-02-03 12:08C++教程网 C/C++

这篇文章主要介绍了C++实现旋转数组的二分查找方法,涉及数组的操作,有值得借鉴的技巧,需要的朋友可以参考下

本文实例讲述了C++实现旋转数组的二分查找方法,分享给大家供大家参考。具体方法如下:

题目要求:

旋转数组,如{3, 4, 5, 1, 2}是{1, 2, 3, 4, 5}的一个旋转,要求利用二分查找查找里面的数。

这是一道很有意思的题目,容易考虑不周全。这里给出如下解决方法:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#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/C++c++ 单线程实现同时监听多个端口

    c++ 单线程实现同时监听多个端口

    这篇文章主要介绍了c++ 单线程实现同时监听多个端口的方法,帮助大家更好的理解和学习使用c++,感兴趣的朋友可以了解下...

    源之缘11542021-10-27
  • C/C++深入理解goto语句的替代实现方式分析

    深入理解goto语句的替代实现方式分析

    本篇文章是对goto语句的替代实现方式进行了详细的分析介绍,需要的朋友参考下...

    C语言教程网7342020-12-03
  • C/C++C语言实现电脑关机程序

    C语言实现电脑关机程序

    这篇文章主要为大家详细介绍了C语言实现电脑关机程序,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...

    xiaocaidayong8482021-08-20
  • C/C++C++之重载 重定义与重写用法详解

    C++之重载 重定义与重写用法详解

    这篇文章主要介绍了C++之重载 重定义与重写用法详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...

    青山的青6062022-01-04
  • C/C++学习C++编程的必备软件

    学习C++编程的必备软件

    本文给大家分享的是作者在学习使用C++进行编程的时候所用到的一些常用的软件,这里推荐给大家...

    谢恩铭10102021-05-08
  • C/C++C语言中炫酷的文件操作实例详解

    C语言中炫酷的文件操作实例详解

    内存中的数据都是暂时的,当程序结束时,它们都将丢失,为了永久性的保存大量的数据,C语言提供了对文件的操作,这篇文章主要给大家介绍了关于C语言中文件...

    针眼_6702022-01-24
  • C/C++详解c语言中的 strcpy和strncpy字符串函数使用

    详解c语言中的 strcpy和strncpy字符串函数使用

    strcpy 和strcnpy函数是字符串复制函数。接下来通过本文给大家介绍c语言中的strcpy和strncpy字符串函数使用,感兴趣的朋友跟随小编要求看看吧...

    spring-go5642021-07-02
  • C/C++C/C++经典实例之模拟计算器示例代码

    C/C++经典实例之模拟计算器示例代码

    最近在看到的一个需求,本以为比较简单,但花了不少时间,所以下面这篇文章主要给大家介绍了关于C/C++经典实例之模拟计算器的相关资料,文中通过示...

    jia150610152021-06-07