首页 > 其他 > 详细

三、二分搜索

时间:2015-07-15 13:06:15      阅读:137      评论:0      收藏:0      [点我收藏+]

二分搜索 

二分搜索的实质上是不断地将有序数据集进行对半分割,并检查每个分区的中间元素。

二分查找的时间复杂度是:O(lgn)

以下是参考《算法精解C语言描述》用C#改写的代码:

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

namespace BiSearch20150715
{
    class Program
    {
        public static void BiSearch(int[] array, int target)
        {
            int left = 0;
            int right = array.Length - 1;
            int mid;
            Array.Sort(array);
            while (left <= right)
            {
                mid = (right - left) / 2 + left;
                if (array[mid] == target)
                {
                    Console.WriteLine("Found at {0}", mid);
                    return;
                }
                else if (array[mid] > target)
                {
                    right = mid - 1;
                }
                else
                {
                    left = mid + 1;
                }
            }
            Console.WriteLine("Not Found");
        }
        static void Main(string[] args)
        {
            int[] array = new int[10] { 1, 2, 4, 5, 6, 9, 11, 3, 8, 12 };
            int target1 = 8;
            int target2 = 13;
            BiSearch(array, target1);
            BiSearch(array, target2);

        }
    }
}

如果传入数组不是有序的,那么不能得出元素在数组中的正确位置。

此代码只做为我的参考

三、二分搜索

原文:http://www.cnblogs.com/holt/p/4647837.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!