二分查找

¥10.00

使用C#实现二分查找算法demo

最佳答案

二分查找,也叫折半查找。粗看起来挺简单,但是也有很多需要注意的细节问题,比如:整数溢出问题、边界查找问题。详细Demo和需要注意的细节参考下面Demo

static void Main(string[] args)
        {

            int[] arrs = new int[200];
            for (int i = 0; i < 200; i++)
            {
                arrs[i] = new Random(i).Next(200);
            }
            Console.WriteLine("数组:" + string.Join(',', arrs));
            Array.Sort(arrs); //数组排序 正序
            Console.WriteLine("排序后数组:" + string.Join(',', arrs));
            int target = new Random().Next(200);
            Console.WriteLine("目标数:" + target);
            int index = new BinSearch().Search(arrs, target, 0, arrs.Length);
            Console.WriteLine(index);
            Console.ReadLine();
}


 /// <summary>
    /// 二分查找、折半查找 demo
    /// </summary>
    public class BinSearch
    {
        /// <summary>
        /// 调用方法前限度数组进行asc排序,左侧为小区 右侧为大区
        /// </summary>
        /// <param name="arrs">已排序数组</param>
        /// <param name="target">要查找的目标书</param>
        /// <param name="start">起始位置 左开</param>
        /// <param name="end">结束位置 右闭  end是数组实际长度 </param>
        /// <returns></returns>
        public int Search(int[] arrs, int target, int start, int end)
        {

            int middle = start + ((end - start) >> 1);
            // >> 值对应二进制右位移一位 避免两个int相加造成溢出

            if (arrs[middle] == target)
            {
                return middle;
            }
            //如果中间数大于目标数,则往中间数左侧查找
            if (arrs[middle] > target)
            {
                end = middle;
            }
            else
            {  //如果中间数小于目标数,则往中间数右侧查找
                start = middle + 1;
            }

            //边界问题 递归何时结束  start>=e
                        

hierror T4 被采纳率73%
2020-07-07 17:31
打赏 0 0
此问题还有以下解决方案
页面统计
429 访问
0 帮助
0.00 打赏
通知消息
  • 暂无任何消息