[C#]演算法-二元搜尋法(Binary Search)

二元搜尋法需要先把要搜尋的數列先排序，由小到大，規則是先取前後二索引數，相加除二，也就是取中間數當索引值，然後跟要搜尋的數字做比較，如果一樣就是找到了，如果中間的數比要搜尋的數大，代表要搜尋的數在左邊數列，右邊數列則放棄，相反之，如果中間數比要搜尋的數小，代表要搜尋的數在右邊數列，左邊數列則放棄。

演算過程的畫面如下程式畫面：

數列串是1,2,3,4,5,6,7,8,9,10,11,12，然後要查詢4這個數字

演算法程式碼如下：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        private static int binarySearch(int[] list,int SearchKey)
        {
            int left = 0 ; 
            int right = list.Length;
            while (left <= right)
            {
                int mid = (left + right) / 2;//取中間位子當基準
                if (list[mid] == SearchKey)
                {
                    return mid;//找到的index值
                }
                else 
                {
                    if (list[mid] < SearchKey)//在右邊的數列
                    {
                        left = mid + 1;
                    }
                    else//在左邊的數列
                    {
                        right = mid - 1;
                    }
                }

            }
            return -1;//找不到時
        }
        static void Main(string[] args)
        {
            int[] list = { 1,2,3,4,5,6,7,8,9,10,11,12};
            Console.WriteLine("原始數字串");
            for (int i = 0; i < list.Length; i++)
            {
                Console.Write(list[i]+" ");
            }
            Console.WriteLine("\r\n請輸入要查詢的數字:");
            int SearchKey = Convert.ToInt32(Console.ReadLine());
            int index = binarySearch(list,SearchKey);
            if (index == -1)
            {
                Console.WriteLine("找不到資料!");
            }
            else
            {
                Console.WriteLine("查到的索引位置:"+index);
            }
            Console.ReadLine();

        }
    }
}

執行結果如下：

 

執行動作過程的程式原始碼如下：

Form1

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace WindowsFormsApplication1
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }


        private void button1_Click(object sender, EventArgs e)
        {
            string value = this.textBox1.Text;

            string search = this.textBox2.Text;
            if (value.Equals(""))
            {
                MessageBox.Show(this, "請先輸入數字串");
            }
            else if (search.Equals(""))
            {
                MessageBox.Show(this, "請先輸入要查詢數字");
            }
            else
            {
                string[] strnum = value.Split(new Char[]{','});
                int[] num = new int[strnum.Length];
                for (int i = 0; i < num.Length; i++)
                {
                    num[i] = System.Convert.ToInt32(strnum[i]);
                }
                int iSearch = System.Convert.ToInt32(search);
                Form2 form2 = new Form2(num,iSearch);
                form2.Visible = true;
            }
        }

    }
}

Form2

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace WindowsFormsApplication1
{
    public partial class Form2 : Form
    {
        private int[] num;
        private int search;
        public Form2()
        {
            InitializeComponent();
            num = new int[0];
            search = -1;
        }
        public Form2(int[] num,int search)
        {
            InitializeComponent();
            this.num = num;
            this.search = search;
        }
        protected override void OnPaint(PaintEventArgs e)
        {
            Font font = new Font("Verdana",14);
            Font font_word = new Font("Verdana", 12);
            SolidBrush brush_check = new SolidBrush(Color.Red);
            SolidBrush brush = new SolidBrush(Color.Blue);
            SolidBrush brush2 = new SolidBrush(Color.Green);
            SolidBrush brush_word = new SolidBrush(Color.Black);
            Graphics g = e.Graphics;
            int top = 20;

            //初始左右二邊
            int left = 0;
            int right = num.Length-1;
            {
                
                int j = 1;
                top = 20;

                while(left<=right)//找不到時會成立
                {

                    g.DrawString("找第 " + (j ) + " 次", font_word, brush_word, 0, top);
                    j++;
                    
                    int mid = (left + right) / 2;//取中間點

                    if (num[mid] == search)
                    {
                        g.DrawString(num[mid].ToString(), font, brush_check, 30 * mid + 90, top);//找到
                        g.DrawString("找到了", font, brush_check, 30 * (mid + 1) + 90, top);//找到
                        return;
                    }
                    else
                    {
                        //中間值有可能在右邊或左邊
                        for (int i = left; i < mid + ((num[mid] < search) ? 1 : 0); i++)
                        {
                            g.DrawString(num[i].ToString(), font, brush, 30 * i + 90, top);
                        }
                        //中間值有可能在右邊或左邊
                        for (int i = right; i > mid-((num[mid] < search) ? 0 : 1); i--)
                        {
                            g.DrawString(num[i].ToString(), font, brush2, 30 * i + 90, top);
                        }
                        //一次切一半
                        if (num[mid]< search)
                        {
                            g.DrawString("左邊不要", font, brush, 30 * (right+1)+90 , top);
                            left = mid + 1;
                        }
                        else
                        {
                            g.DrawString("右邊不要", font, brush, 30 * (right + 1)+90, top);
                            right = mid - 1;
                        }
                    }
                    top = 20 * j;//印到下一行    
                }
            }
            g.DrawString("找不到", font, brush_check, 0, top+20);//找到
        }
       
    }
}

原始碼及執行程式下載