Универсальный двоичный поиск


У меня есть следующий код для двоичного поиска

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

namespace BinarySearch
 {
    public class IntComparer : Comparer<int>
    {
        public override int Compare(int x, int y)
        {
            if (x == y)
            {
                return 0;
            }
            else if (x > y)
            {
                return 1;
            }
            else
            {
                return -1;
            }
        }
    }

    public static class BinarySearcher
    {
        public static bool BinarySearch(this int[] array, int value)
        {
            uint bottom = 0;
            uint top = (uint)array.Length - 1;
            uint middle = top >> 1;
            while (top >= bottom)
            {
                if (array[middle] == value)
                {
                    return true;
                }
                else if (array[middle] > value)
                {
                    top = middle - 1;
                }
                else
                { 
                    bottom = middle + 1; 
                }
                middle = (bottom + top) >> 1; //to avoid overflow
            }
            return false;       
        }

        public static bool BinarySearch<T>(T item, T[] array, IComparer<T> comparer)
        {
            uint bottom = 0;
            uint top = (uint)array.Length - 1;
            uint middle = top >> 1;
            while (top >= bottom)
            {
                int compareResult = comparer.Compare(array[middle], item);

                if (compareResult == 0)
                {
                    return true;
                }
                else if (compareResult > 0)
                {
                    top = middle - 1;
                }
                else
                { 
                    bottom = middle + 1; 
                }
                middle = (bottom + top) >> 1; // middle = bottom + ((top - bottom) / 2); ?
            }
            return false;
        }

        public static bool BinarySearchRec<T>(T item, T[] array, IComparer<T> comparer)
        {
            uint bottom = 0;
            uint top = (uint)array.Length - 1;
            return BinarySearchRec<T>(item, array, comparer, bottom, top);
        }

        private static bool BinarySearchRec<T>(T item, T[] array, IComparer<T> comparer, uint bottom, uint top)
        {
            if (bottom > top)
            {
                return false;
            }
            uint middle = (bottom + top) >> 1; 
            int compareResult = comparer.Compare(array[middle], item);
            if (compareResult > 0)
            {
                return BinarySearchRec(item, array, comparer, bottom, middle - 1);
            }
            else if (compareResult < 0)
            {
                return BinarySearchRec(item, array, comparer, middle + 1, top);
            }
            else
            {
                return true;
            }
        }
    }

    class Program
    {
        private const int ITERATIONS = 1000000;

        static void Main(string[] args)
        {
            int[] sortedArray = {1,2,3,4,5,6,7,8,9,10};
            Console.WriteLine(BinarySearcher.BinarySearch<int>(10, sortedArray, new IntComparer()));

            Console.WriteLine(BinarySearcher.BinarySearchRec<int>(14, sortedArray, new IntComparer()));

            Console.WriteLine(sortedArray.BinarySearch(1));

            int[] sortedArray2 = new int[ITERATIONS];
            for (int i = 0; i < ITERATIONS; i++)
            {
                sortedArray2[i] = i;
            }

            Stopwatch stopWatch = new Stopwatch();
            stopWatch.Start();
            for (int i = 0; i < ITERATIONS; i++)
            {
                sortedArray2.BinarySearch(0);
            }
            stopWatch.Stop();
            Console.WriteLine("Time required for execution: " + stopWatch.ElapsedMilliseconds + "ms");

            stopWatch.Reset();
            stopWatch.Start();
            for (int i = 0; i < ITERATIONS; i++)
            {
                BinarySearcher.BinarySearchRec<int>(0, sortedArray2, new IntComparer());
            }
            stopWatch.Stop();
            Console.WriteLine("Time required for execution: " + stopWatch.ElapsedMilliseconds + "ms");

            stopWatch.Reset();
            stopWatch.Start();
            for (int i = 0; i < ITERATIONS; i++)
            {
                BinarySearcher.BinarySearch<int>(0, sortedArray2, new IntComparer());
            }
            stopWatch.Stop();
            Console.WriteLine("Time required for execution: " + stopWatch.ElapsedMilliseconds + "ms");

            Console.ReadLine();

        }
    }
}

Я должен добавить, проверка ввода пользователя

Что является лучшим способом, чтобы реализовать общие метод для бинарного поиска? Может быть, есть лучший способ сделать так, а не с компаратора?



4625
2
задан 27 ноября 2011 в 10:11 Источник Поделиться
Комментарии
2 ответа

Если вопрос такого рода всплывает на собеседовании, это может быть вопрос с подвохом, и вы, возможно, должны демонстрировать, что вы осознаете о том, чтобы не изобретать заново колесо. Большую часть стоимости .Чистая является то, что это очень богатая среда, которая обеспечивает программистов с большим количеством вещей, уже встроены и готовы к использованию, (не говоря уже протестированы, отлажены и известные проблемы-бесплатные работы,) так необходимый навык для .Net программиста-это знать, что уже есть, так что они не тратить время на повторное внедрение времени и отладки.

Если вы можете исключить сценарий каверзный вопрос, то вот что я скажу:


  1. Сделайте свой метод возвращает тип int, а не bool значение, как встроенный двоичный поиск, методы.

  2. Сделать дополнительную перегрузку, которая работает с системой.Сравнение вместо системы.Интерфейса icomparer.

  3. Сделать дополнительную перегрузку, которая работает с ни сравнения ни интерфейса icomparerно вместо этого он предполагает, что Т реализует интерфейс icomparable.

  4. Держать средний = вниз + ((верх - низ) / 2) часть, она должна избежать арифметическое переполнение, если случайно вы не сортировка массива с невероятно большим количеством элементов. (Не очень важно, но это показывает внимание к деталям.)

  5. Код общественного переопределить int и сравниваем(тип int х, int и г) метод следующим образом:
    { возвращение Х - Y; } ;-)

1
ответ дан 28 ноября 2011 в 12:11 Источник Поделиться

Лучший способ реализации общедоступного универсального метода для бинарного поиска, вызывая ищет() метод системы.Массив. (Еще лучше, не реализовать такой метод на всех, и вызов системе.Массив.Ищет() напрямую.)

0
ответ дан 28 ноября 2011 в 08:11 Источник Поделиться