循环有序数组的二分查找

亚马逊面试题:给定一个循环有序数组,形如 [9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 0, 1, 2, 3, 4, 5, 6, 7, 8] ,在其中查找某个元素。

最简单直接朴素的算法,从头至尾依次遍历,复杂度O(n)。如果只能做到这样的话,就不必再说了。 对于普通的有序数组,通常会采用二分法查找元素,这样复杂度可以降低至O(logN)。但是这个循环的有序数组的最大最小部分在数组中间而不是在头尾,是否还可以采用二分法查找呢? 普通的二分法思路是:在中间取一元素,与要查找的目标元素对比,若中间元素较大,则在左半部继续二分法查找;反之,若中间元素较小,则在右半部继续二分法查找。如下:

/* 
   p is the start index, 
   q is the end index, 
   x is the target data 
*/
int binary_search(int x, int p, int q, int *a) {
    if (p >= q && a[p] != x)
        return -1;

    int m = (p + q) / 2;

    if (a[m] == x)
        return m;

    if (x > a[m])
        p = m + 1;
    else
        q = m - 1;

    return binary_search(x, p, q, a);
}

该算法应用到这个循环数组上的时候,以在数组[9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 0, 1, 2, 3, 4, 5, 6, 7, 8]中查找元素 0 为例,第一步取中间第 9 个元素值为 18 :

search: 0        |   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  
----------------------------------------------------------------------------------------------------
p= 0, m= 9, q=19 |   9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,  0,  1,  2,  3,  4,  5,  6,  7,  8,

此时目标元素 0 小于中间元素 19,该如何判断下一步是应该在左半边查找还是在右半边查找呢?仔细观察该数组,在下标9处被分为两个部分,左边为[9, 10, ..., 18],右边为[19, 0, ..., 8]。以目测的结果来看,应该在右半边继续查找,与原始二分法的判断结果恰好相反。原始的算法,只能应用于一个单调递增的数组,而循环数组则将一个单调递增数组变成了两个单调递增数组。第一部取完中点之后,数组被分为两个部分。一般的情况下,一部分必然为单调递增,一部分为非单调递增(含有断点)。很容易想到,如果目标元素在单调递增那一部分,则可继续在此区间查找,此区间内的查找则是原始的二分查找;如果目标元素在非单调递增部分,则又还原成了原问题,只是查找范围缩小了一半。重复这个过程,则可以得到查找结果。

search : 0       |  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  
----------------------------------------------------------------------------------------------------
p= 0, m= 9, q=19 |  9, 10, 11, 12, 13, 14, 15, 16, 18, 18, 19,  0,  1,  2,  3,  4,  5,  6,  7,  8, 
p=10, m=14, q=19 |                                         19,  0,  1,  2,  3,  4,  5,  6,  7,  8, 
p=10, m=11, q=13 |                                         19,  0,  1,  2, 
result: 11

在这个过程中,需要注意几个个问题:

  1. 如何判断一段数组是单调递增呢?在该段数组的头、中间、尾三个位置p,m,q取三个值a[p], a[m], a[q],如果是单调递增则一定满足 a[p] >= a[m] >= a[q],否则则非单调递增。

  2. 判断目标元素下一步所在区间,有几种情况:

    • 当 x > a[m] 时,
      • 右半边是单调递增区间,并且x在此区间内,下一步则可在此右半边区间内查找
      • 右半边是单调递增区间,并且x不在此区间内,下一步在左半边查找
      • 右半边是非单调递增区间,则x必然在此区间内,下一步在右半边查找
    • 当 x < a[m] 时, 同理类似
      • 左半边是单调递增区间,并且x在此区间内,下一步则可在此左半边区间内查找
      • 左半边是单调递增区间,并且x不在此区间内,下一步在右半边查找
      • 左半边是非单调递增区间,则x必然在此区间内,下一步在左半边查找
  3. 判断是否在单调递增部分,只需与区间的另外一头的元素比较一下大小即可知道

样例代码:

#include <stdio.h>

#define N 20
int arr[N] = {9,10,11,12,13,14,15,16,17,18,19,0,1,2,3,4,5,6,7,8};

void print_header(int target) {
    printf("search :%2d %*c | ", target, 5, ' ');
    for (int i = 0; i < N; i++) {
        printf("%2d  ", i);
    }
    printf("\n");
    for (int i = 0; i< N; i++) {
        printf("-----");
    }
    printf("\n");
}

void print_array(int p, int m, int q, int *a) {
    printf("p=%2d, m=%2d, q=%2d |%*c", p, m, q, 4 * p + (p>0?1:0), ' ');
    for (int i = p; i <= q; i++) {
        printf("%2d, ", a[i]);
    }
    printf("\n");
}

/* 非递归方式 */
int search_loop_array(int x, int* a, int length) {
    int p = 0;
    int q = length - 1;

    while ( p <= q ) {
        int m = ( p + q ) / 2;

        print_array(p, m, q, a);

        if ( x == a[m] )
            return m;

        if ( x > a[m] ) {
            int mm = ( m + q ) / 2;
            int increase = (a[m] <= a[mm] && a[mm] <= a[q]);
            if ( ( increase && x <= a[q] ) || ! increase)
                p = m + 1;
            else
                q = m - 1;
        } else {
            int mm = ( p + m ) / 2;
            int increase = a[p] <= a[mm] && a[mm] <= a[m];
            if ( increase && x >= a[p] || !increase) 
                q = m - 1;
            else
                p = m + 1;
        }
    }

    return -1;
}

/* 递归方式 */
int search_loop_array2(int x, int low, int high, int* a) {
    if (low >= high && a[low] != x)
        return -1;

    int m = (low + high) / 2;

    print_array(low, m, high, a);

    if ( x == a[m] )
        return m;

    if ( x > a[m] ) {
        int mm = (m + high) / 2;
        int increase = (a[m] <= a[mm] && a[mm] <= a[high]);

        if ( !increase || (increase && x <= a[high] ) )
            low = m + 1;
        else
            high = m - 1;

    } else {
        int mm = (low + m) / 2;
        int increase = (a[low] <= a[mm] && a[mm] <= a[m]);

        if ( !increase || (increase && x >= a[low] ) )
            high = m - 1;
        else
            low = m + 1;
    }

    return search_loop_array2(x, low, high, a);
}

int main() {

    for (int i = 0; i < N; i++) {
        print_header(i);

        // printf("result: %d\n\n", search_loop_array(i, arr, N));
        printf("result: %d\n\n", search_loop_array2(i, 0, N-1, arr));
    }
    return 0;
}

完。

SharpDevelop的AddInTree View 插件

自从SharpDevelop 源码分析的系列文章发出来之后,很多朋友给了不错的评价,在这里先感谢各位朋友的鼓励。另外,评论中有位朋友想看看我在文章中提到的AddInTreeView插件,其实这个是个很简单的小东西,因此单独发在这里了。(好像没有找到那里能上传文件,因此直接贴代码了)

AddinTreeViewCommand.cs

/* 
 * Created by SharpDevelop. 
 * User: Administrator 
 * Date: 2004-10-4 
 * Time: 4:12 
 *  
 * To change this template use Tools | Options | Coding | Edit Standard Headers. 
 */ 
using System; 
using System.Windows.Forms; 
using System.CodeDom.Compiler; 

using ICSharpCode.SharpDevelop.Gui; 
using ICSharpCode.SharpDevelop.Gui.Pads; 
using ICSharpCode.Core.AddIns; 
using ICSharpCode.Core.AddIns.Codons; 
using ICSharpCode.SharpDevelop.Services; 

namespace Addins.AddinTreeView 
{ 
    /// <summary> 
    /// Description of MyClass. 
    /// </summary> 
    public class AddinTreeViewCommand: AbstractMenuCommand 
    {     
        public override void Run() 
        {     
            using (AddinTreeViewContent viewContent = new AddinTreeViewContent() ) 
            { 
                WorkbenchSingleton.Workbench.ShowView(viewContent); 
            } 
        }         
    } 

    public class AddinTreeViewContent: AbstractViewContent 
    { 
        AddinTreeViewControl viewControl = new AddinTreeViewControl(); 

        public override Control Control  
        { 
            get  
            { 
                return viewControl; 
            } 
        } 

        public override bool IsDirty  
        { 
            get  
            { 
                return false; 
            } 
            set  
            { 
            } 
        } 

        IWorkbenchWindow workbenchWindow; 
        public override IWorkbenchWindow WorkbenchWindow  
        { 
            get  
            { 
                return workbenchWindow; 
            } 
            set  
            { 
                workbenchWindow = value; 
                workbenchWindow.Title = "AddInTreeView"; 
            } 
        } 

        public AddinTreeViewContent() 
        { 
            TitleName = "AddinTree View"; 
        } 


        public override bool IsViewOnly  
        { 
            get  
            { 
                return true; 
            } 
        } 
        public void SaveFile(){} 
        public void Undo(){} 
        public void Redo(){} 
        public override void Save(){} 
        public override void Save(string filename){} 
        public override void Load(string filename) 
        { 
        } 

        public override string TabPageText  
        {  
            get  
            { 
                return "AddInTree"; 
            } 
        } 

    } 
} 

AddinTreeViewControl.cs

using System; 
using System.Collections; 
using System.ComponentModel; 
using System.Drawing; 
using System.Data; 
using System.Windows.Forms; 

using ICSharpCode.SharpDevelop.Gui; 
using ICSharpCode.Core.AddIns; 
using ICSharpCode.Core.AddIns.Codons; 

namespace Addins.AddinTreeView 
{ 
    /// <summary> 
    /// AddinTreeViewControl 的摘要说明。 
    /// </summary> 
    public class AddinTreeViewControl : System.Windows.Forms.UserControl 
    { 
        private System.Windows.Forms.ColumnHeader chName; 
        private System.Windows.Forms.ListView lvAddin; 
        private System.Windows.Forms.ColumnHeader chInfo; 
        private System.Windows.Forms.CheckBox cbShowAddinInfo; 
        private System.Windows.Forms.Splitter splitter2; 
        private System.Windows.Forms.ListView lvDebug; 
        private System.Windows.Forms.Splitter splitter1; 
        private System.Windows.Forms.TreeView tvAddin; 
        private System.Windows.Forms.ColumnHeader chValue; 
        /// <summary>  
        /// 必需的设计器变量。 
        /// </summary> 
        private System.ComponentModel.Container components = null; 

        public AddinTreeViewControl() 
        { 
            // 该调用是 Windows.Forms 窗体设计器所必需的。 
            InitializeComponent(); 

            // TODO: 在 InitializeComponent 调用后添加任何初始化 
            InitAddinTreeView(); 
        } 

        /// <summary>  
        /// 清理所有正在使用的资源。 
        /// </summary> 
        protected override void Dispose( bool disposing ) 
        { 
            if( disposing ) 
            { 
                if(components != null) 
                { 
                    components.Dispose(); 
                } 
            } 
            base.Dispose( disposing ); 
        } 

        组件设计器生成的代码 


        void InitAddinTreeView() 
        { 
            TreeNode pathNode = tvAddin.Nodes.Add("AddinRoot"); 

            tvAddin.BeginUpdate(); 
            try 
            { 
                foreach ( AddIn addIn in AddInTreeSingleton.AddInTree.AddIns) 
                { 
                    foreach ( ICSharpCode.Core.AddIns.AddIn.Extension e in addIn.Extensions) 
                    { 
                        string [] paths = e.Path.Split('/'); 
                        pathNode = tvAddin.Nodes[0]; 

                        for ( int i=0; i<paths.Length; i++) 
                        {     
                            bool foundPath = false; 

                            if ( paths[i] == "" )  
                            { 
                                pathNode = tvAddin.Nodes[0]; 
                                continue; 
                            }                         

                            for ( int j=0; j<pathNode.Nodes.Count; j++) 
                            { 
                                if ( pathNode.Nodes[j].Text == paths[i] ) 
                                { 
                                    pathNode = pathNode.Nodes[j]; 
                                    foundPath = true; 
                                    break; 
                                } 
                            } 

                            if ( !foundPath ) 
                            { 
                                pathNode = pathNode.Nodes.Add( paths[i] ); 
                                pathNode.Tag = new ArrayList(); 
                                //lvDebug.Items.Add("Add " + e.Path + " ---- " + paths[i]); 
                            } 
                        } 

                        (pathNode.Tag as ArrayList).Add(e); 
                    } 
                } 
            } 
            finally 
            { 
                tvAddin.EndUpdate(); 
            } 
        } 

        void AddInfo(string Name, string Value) 
        { 
            lvAddin.Items.Add(Name).SubItems.Add(Value); 
        } 

        private void tvAddin_AfterSelect(object sender, System.Windows.Forms.TreeViewEventArgs e) 
        { 
            lvAddin.Items.Clear(); 

            if ( e.Node.Tag != null ) 
            { 
                foreach (AddIn.Extension et in (e.Node.Tag as ArrayList)) 
                { 
                    AddInfo("Extension", et.ToString()); 

                    foreach ( ICodon codon in et.CodonCollection) 
                    { 
                        AddInfo("  ┏ Codon ID", codon.ID); 
                        AddInfo("  ┣ Codon Name", codon.Name); 
                        AddInfo("  ┗ Codon Class", codon.Class); 

                        if ( cbShowAddinInfo.Checked ) 
                        { 
                            AddInfo("      ┣ Addin Name", codon.AddIn.Name); 
                            AddInfo("      ┗ Addin FileName", codon.AddIn.FileName); 

                            foreach ( ICSharpCode.Core.AddIns.AddIn.Extension ex in codon.AddIn.Extensions) 
                            { 
                                AddInfo("          ┣ Addin Extensions", ex.Path); 
                            } 
                            AddInfo("          ┗━━━━━━━━━", ""); 
                        } 
                    } 
                } 
            } 
        } 
    } 
}