滴水逆向联盟

标题: 基于visual Studio2013解决面试题之0309左移递减序列搜索 [打印本页]

---

作者: 大灰狼    时间: 2014-7-30 08:34
标题: 基于visual Studio2013解决面试题之0309左移递减序列搜索




题目

解决代码及点评

• <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://www.dtdebug.com/)

Powered by Discuz! X3.2