C#中的二分查找

Question

我正在尝试对具有 10 个数字的随机数组进行二分搜索。当我运行我的代码时，我输入的数字是随机数组中的一个数字，而不是只输出一次“找到它”，它会不断输出“找到”直到我关闭程序，但我不明白是什么我已经做了让它继续输出“找到它”。

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

namespace Binary_Search
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 10; //10 values in array
            Random r = new Random();

            int b; //value to search
            int i; //loop control value

            int[] a = new int[n + 1];

            a[0] = 0; //starts at 0

            for (i = 1; i <= n; i++) // set the array up
                a[i] = a[i - 1] + r.Next(1, 10); // + random numbers from 1 to 10

            for (i = 1; i <= n; i++) 
                Console.WriteLine(" a[" + i + "] + " + a[i] + ": "); // outputs the numbers for each value of array

            Console.WriteLine();
            Console.ReadLine();

            Console.WriteLine("What number are you looking for?");

            b = int.Parse(Console.ReadLine()); // enter value that you want to find

            i = 1;

            Console.ReadLine();

            int min = 1;
            int max = n - 1;

            do
            {
                int mid = (min + max) / 2;

                if (a[mid] == b)
                {
                    Console.WriteLine("Found it");
                }
                else if (a[mid] > b)
                    max = mid;
                else if (a[mid] < b)
                    min = mid;
            } while (min <= max);

            Console.ReadLine();
        }
    }
}

Answer 1

由于您的 do-while 条件，“找到它”消息不断打印。您进入无限循环，因为经过多次迭代后，min等于max。将条件设置为while (min < max);而不是，while (min <= max);并在循环后设置 if 条件。

这应该可以解决问题：

do
{
     int mid = (min + max) / 2;
     if (a[mid] > b)
         max = mid;
     else if (a[mid] < b)
         min = mid;
} while (min < max);

if (a[mid] == b)
{
     Console.WriteLine("Found it");
}