滴水逆向联盟
标题: 基于visual Studio2013解决面试题之0309左移递减序列搜索 [打印本页]
作者: 大灰狼 时间: 2014-7-30 08:34
标题: 基于visual Studio2013解决面试题之0309左移递减序列搜索
本帖最后由 大灰狼 于 2014-7-30 08:37 编辑
题目
解决代码及点评
- <pre code_snippet_id="110766" snippet_file_name="blog_20131213_1_9206031" class="cpp" name="code"><pre code_snippet_id="110766" snippet_file_name="blog_20131213_1_9206031" class="cpp" name="code"><pre code_snippet_id="110766" snippet_file_name="blog_20131213_1_9206031" class="cpp" name="code"><pre code_snippet_id="110766" snippet_file_name="blog_20131213_1_9206031" name="code" class="cpp"><pre code_snippet_id="110766" snippet_file_name="blog_20131213_1_9206031" name="code" class="cpp"><pre code_snippet_id="110766" snippet_file_name="blog_20131213_1_9206031" name="code" class="cpp">/*
- 左移递减数列查找某一个数
- 左移递减数列,指一个数列是由一个递减数列左移而来
- 比如[6,5,4,3,2,1] 左移两位得到[4,3,2,1,6,5]
- 在左移数列中查找某一个数
-
- 想法:依旧可以用二分查找法,因为这样的数列二分之后,至少有一半是有序的
- */
-
- #include <iostream>
- using namespace std;
-
- // 这个函数是一个有序序列的二分查找,不再多加注释了,大家自己看吧
- int bsearch(int arr[], int start, int end, int value)
- {
- if (start == end)
- {
- if (arr[start] == value)
- return start;
- return -1;
- }
- int mid = (start + end) / 2;
-
- if (arr[mid] == value)
- return mid;
-
- if (value > arr[mid])
- {
- return bsearch(arr, start, mid-1, value);
- }
- return bsearch(arr, mid+1, end, value);
- }
-
- // 不严格的二分查找
- int search(int arr[], int start, int end, int value)
- {
- // 结束条件之一,如果start和end相当,则必须要返回
- if (start == end)
- {
- if (arr[start] == value)
- return start;
- return -1;
- }
-
- // 如果mid下标对应正好是要查找的值,也返回
- int mid = (start + end) / 2;
- if (arr[mid] == value)
- return mid;
-
- // 当前半段有序时
- if (arr[mid] < arr[start])
- {
- // 检查value是不是在前半段,如果是,则进入严格的二分查找程序
- if (arr[mid] < value && arr[start] > value)
- {
- // 严格的二分查找
- return bsearch(arr, start, mid-1, value);
- }
-
- // 如果不是在前半段,那有可能在后半段,后半段也是个左移递减序列,所以递归调用自己
- return search(arr, mid+1, end, value);
- }
-
- // 如果前半段不是有序,那么后半段必然有序
- if (arr[mid] > value && arr[end] < value) // 检查value是不是在后半段,如果是,则在后半段中执行严格的二分查找
- {
- // 严格的二分查找
- return bsearch(arr, mid+1, end, value);
- }
-
- // 如果不在后半段,那么在左移递减序列的前半段查找
- return search(arr, start, mid-1, value);
- }
-
- int main()
- {
- int nArr[10] = {4,3,2,1,6,5};
- cout << search(nArr, 0, 5, 6);
- system("pause");
- return 0;
- }</pre><br></pre><br></pre><br></pre></pre></pre>
代码下载及其运行代码下载地址:http://download.csdn.net/detail/yincheng01/6704519
解压密码:c.itcast.cn
下载代码并解压后,用VC2013打开interview.sln,并设置对应的启动项目后,点击运行即可,具体步骤如下:
1)设置启动项目:右键点击解决方案,在弹出菜单中选择“设置启动项目”
2)在下拉框中选择相应项目,项目名和博客编号一致
3)点击“本地Windows调试器”运行
程序运行结果
欢迎光临 滴水逆向联盟 (http://dtdebug.com/) |
Powered by Discuz! X3.2 |