Я не могу написать бинарный поиск

    Недавно (буквально два года назад) тут пробегала статья Только 10% программистов способны написать двоичный поиск. Двоичный поиск — это классический алгоритм поиска. Мало того, это еще чрезвычайно простой алгоритм, который можно очень легко описать: берем отсортированный массив, смотрим в середину, если не нашли там число, в зависимости от того, что в середине — ищем это число этим же методом либо в левой части, либо в правой, откидывая средний элемент. Для функций также, просто берем не массив, а функцию. Все очень и очень просто, алгоритм описан почти везде, все баги словлены и описаны.

    Так вот, я не могу реализовать двоичный поиск. Для меня он ни капельки не тривиален. Наверное, я ненастоящий программист. А ведь так и есть, я всего-лишь студент, но ведь это не оправдание? Если точнее, я не могу реализовать хороший корректный красивый двоичный поиск. Все время у меня вылезает проблема либо с корректностью, либо с красивостью, либо и с тем, и с другим. Так что, да, заголовок немного желтоват.
    Прежде чем читать этот топик, напишите свою версию бинарного поиска — для отсортированного массива. Причем, в зависимости от параметра, поиск должен выдавать или первый элемент, или любой из дублирующих. Еще для сравнения, напишите бинарный поиск для функций

    Для начала, я буду писать код на C#. Я надеюсь, поклонники других языков с легкостью поймут мой код. Границы поиска я буду представлять в виде полуинтервала [left; right), т.е. точка left включается, а точка right выключается. Для меня полуинтервалы удобнее, к их поведению я уже привык, кроме того, использование полуинтервалов имеет некоторые преимущества при программировании различных алгоритмов (о чем мы поговорим позже). Вообще, использовать полуинтервалы более правильно с точки зрения поддержки «единого стиля программирования», так как я пишу циклы вот так:
    for (int i = 0; i < array.Length; i++)
    а не так:
    for (int i = 0; i <= array.Length - 1; i++)

    Я буду писать одновременно рекурсивную и итеративную версию, но мне ближе рекурсивная, так что не обессудьте. Для рекурсивной версии мы сделаем вот такую вот красивую обертку:
    static int BinarySearch_Rec_Wrapper(int[] array, int element)
    {
        BinarySearch_Rec(array, element, 0, array.Length);
    }


    Первая попытка


    Итак, давайте напишем первую версию бинпоиска для отсортированного массива. Для начала, нам нужно уметь вычислять индекс среднего элемента. Окей, допустим мы очень умные и уже знаем, что обычный способ
    int mid = (left + right) / 2 
    вызовет переполнение на больших массивах, и поэтому будем использовать более правильный метод (см. ссылку в начале статьи):
     int mid = left + (right - left) / 2

    При разработке алгоритмов очень полезно рисовать на листочке пример входных данных, ваши действия и результат. Иначе рискуете нарваться на ошибку типа off-by-one. К примеру, для первого шага можно нарисовать такую картинку:

    Это дает хорошее понимание, что массив надо бить на интервал от [0, 3) и от [4, 7), т.е. от [left, mid) и до [mid + 1, right). Надо заметить, что существовала еще и «нулевая» версия (для статьи), в которой индексы были написаны по памяти, и, естественно, написаны они были неправильно. Самое интересное, что если я пишу алгоритм на листочке, то никаких ошибок не появляется, а если пишу на компьютере, они вылазят как грибы после дождя.

    Кстати, теперь можно добавить еще одну причину к использованию полуинтервалов: если у нас есть интервал [left, right], то мы должны его разбить на [left, mid — 1] и [mid + 1; right] (что конечно, чуть проще для запоминания, но весьма странно).
    У полуинтервалов различие в индексах равно 1 (одному элементу, который мы выбрасываем), а у интервалов — 2 — магической цифре, взятой с потолка.

    Особенно это заметно для сортировки слиянием, где для полуинтервалов различия в индексах нету (массив делится на [left, mid) и [mid, right)), а для интервалов появляется различие равное 1 (так как массив делится на [left, mid] и [mid + 1, right], или [left, mid — 1] и [mid, right]).

    Теперь, осталось определить, в какой части массива нужно искать элемент, в зависимости от того, меньше ли средний элемент (array[mid]), чем ключ (key). Сделать это весьма просто — нужно просто подставить сначала один знак, проверить, работает ли программа, а если не работает, то другой :-). Почему-то именно такой способ проверки я и использую. Мне постоянно кажется, что перекомпилировать быстрее, чем «подумать».
    Рекурсивно:
    
    static int BinarySearch_Rec(int[] array, int key, int left, int right)
    {
        int mid = left + (right - left) / 2;
    
        if (array[mid] == key)
            return mid;
    
        else if (array[mid] > key)
            return BinarySearch_Rec(array, key, left, mid);
        else
            return BinarySearch_Rec(array, key, mid + 1, right);
    }
    
    Итеративно:
    
    static int BinarySearch_Iter(int[] array, int key)
    {
        int left = 0;
        int right = array.Length;
    
        while (true)
        {
            int mid = left + (right - left) / 2;
    
            if (array[mid] == key)
                return mid;
    
            if (array[mid] > key)
                right = mid;
            else
                left = mid + 1;
        }
    }
    


    Разбор полетов:
    Если внимательно вчитаться в итеративную версию программы, то сразу становится понятно, что если элемента нет, то алгоритм никогда не остановится. Пониманию этого факта очень способствует while(true), которого в рекурсивной версии программы, естественно нет. И хотя я написал кучу реализаций рекурсивных алгоритмов, я все еще иногда сталкиваюсь с тем, что забываю остановить рекурсию. Как можно написать итеративную версию с подвохом, я не знаю.

    Вторая попытка


    Хорошо, нам надо останавливать алгоритм, когда мы не можем найти элемент в массиве. Но мы же должны что-то возвратить, верно? Или хотя-бы кинуть исключение. Что возвратить? Может быть магическое число (к примеру, -1)? Или заменить int на int? и возвратить null? (int? в c# — это число, которому можно присвоить null). Или может быть вернуть предполагаемое место в массиве, где мог-бы быть элемент, но его нет? Или все-таки кинуть исключение? Или… Это достаточно интересный вопрос, почти такой же как и «в чем смысл жизни?». Кроме интересности, эти вопросы объединяет тот факт, что ответ на оба вопроса можно сформулировать следующим образом: что хотите, то и выбирайте. Конечно, найдутся люди, которые скажут, что нужно возвращать только null, и только null.

    Я предпочитаю в таком случае возвратить специальное число -(1 + left), так как, бинарный поиск может использоваться для того, чтобы вставить новый элемент, и потеря информации будет вредна. Конечно, можно написать две версии алгоритма — одна будет возвращать специальное число, а вторая кидать исключение. Хотя это и нехорошо для принципа DRY, если в вашем языке нету чего-нибудь мощного вроде макросов, которые создают функции при компиляции. Ну или можно засунуть в алгоритм параметр, обозначающий что делать.

    Кстати, останавливать рекурсию мы будем в случае left == right, т.е., когда интервал стал таким — [left, right). Ну или в случае, когда right — left < 1 или right — left <= 0. Последний, кстати, полезнее, поскольку нам могли передать что-то не то в функцию (в итеративную версию, там где нету обертки).

    Рекурсивно:
    
    static int BinarySearch_Rec(int[] array, int key, int left, int right)
    {
        int mid = left + (right - left) / 2;
    
        if (left >= right)
            return -(1 + left);
    
        if (array[mid] == key)
            return mid;
    
        else if (array[mid] > key)
            return BinarySearch_Rec(array, key, left, mid);
        else
            return BinarySearch_Rec(array, key, mid + 1, right);
    }
    
    Итеративно:
    
    static int BinarySearch_Iter(int[] array, int key)
    {
        int left = 0;
        int right = array.Length;
        int mid = 0;
    
        while (!(left >= right))
        {
            mid = left + (right - left) / 2;
    
            if (array[mid] == key)
                return mid;
    
            if (array[mid] > key)
                right = mid;
            else
                left = mid + 1;
        }
    
        return -(1 + left);
    }
    


    Разбор полетов:
    Нам никто не говорил, что массив отсортирован по возрастанию. Поэтому нам нужно вычислить, в каком порядке находятся числа в массиве, и уже в зависимости от этого выбирать нужную половину для поиска. Кстати, вычислять нужно всего-лишь раз, так что к итеративной версии тоже придется дописывать обертку.

    Попытка №3


    Нужно придумать, как выбирать нужную половину для поиска. Самая первая моя попытка содержала и ||, и &&, после чего мне повезло заметить, что все это сводится к банальнейшему XOR'у:
    descendingOrder array[mid] > key XOR
    0 0 0
    0 1 1
    1 0 1
    1 1 0

    Т.е. если флаг descendingOrder не установлен, то выбор идет как обычно, если установлен, то выбор идет наоборот. Но это «хак», и возможно, что нужно написать какой-нибудь комментарий. Я не знаю, что именно он должен содержать.
    Рекурсивно:
    
    static int BinarySearch_Rec(int[] array, bool descendingOrder, int key, int left, int right)
    {
        int mid = left + (right - left) / 2;
    
        if (left >= right)
            return -(1 + left);
    
        if (array[mid] == key)
            return mid;
    
        else if ((array[mid] > key) ^ descendingOrder)
            return BinarySearch_Rec(array, descendingOrder, key, left, mid);
        else
            return BinarySearch_Rec(array, descendingOrder, key, mid + 1, right);
    }
    
    static int BinarySearch_Rec_Wrapper(int[] array, int key)
    {
    	if (array.Length == 0)
            return -1;
    
        bool descendingOrder = array[0] > array[array.Length - 1];
        return BinarySearch_Rec(array, descendingOrder, key, 0, array.Length);
    }
    
    Итеративно:
    
    static int BinarySearch_Iter(int[] array, bool descendingOrder, int key)
    {
        int left = 0;
        int right = array.Length;
        int mid = 0;
    
        while (!(left >= right))
        {
            mid = left + (right - left) / 2;
    
            if (array[mid] == key)
                return mid;
    
            if ((array[mid] > key) ^ descendingOrder)
                right = mid;
            else
                left = mid + 1;
        }
    
        return -(1 + left);
    }
    
    static int BinarySearch_Iter_Wrapper(int[] array, int key)
    {
    	if (array.Length == 0)
        	return -1;
    
        bool descendingOrder = array[0] > array[array.Length - 1];
        return BinarySearch_Iter(array, descendingOrder, key);
    }
    


    Разбор полетов:
    На всякий случай: один из вариантов проверки направления сортировки не учитывал, что массив может быть пуст. Я решил не выделять этот фейл в отдельную попытку.

    Попытка №4


    Теперь нужно сделать так, чтобы алгоритм искал первый элемент из равных. Для этого надо додуматься как минимум до одной «нетривиальной» идеи — не выбрасывать из области поиска уже найденный элемент, если у нас нет других кандидатов. Не знаю, что было со мной, когда я первый раз пытался это реализовать… Но я не догадался до этого.
    Нарисуем шаг, когда мы уже нашли один элемент, который равен ключу и нам нужно найти первый элемент из одинаковых:

    Дабы мы не попали на еще одну попытку, сразу скажу, что теперь рекурсию нужно останавливать еще и в случае, когда самый первый элемент из полуинтервала равен ключу. Ну а в случае, когда мы узнали, что средний элемент равен ключу у нас есть два варианта. Либо средний следует за первым и нужно выдавать именно его, ибо первый не равен ключу, поскольку рекурсия еще не остановилась. Либо нужно укорачивать область поиска (см. картинку выше)

    Рекурсивно:
    
    static int BinarySearch_Rec(int[] array, bool descendingOrder, int key, int left, int right)
    {
        int mid = left + (right - left) / 2;
    
        if (left >= right)
            return -(1 + left);
    
        if (array[left] == key)
            return left;
    
        if (array[mid] == key)
        {
            if (mid == left + 1)
                return mid;
            else
                return BinarySearch_Rec(array, descendingOrder, key, left, mid + 1);
        }
    
        else if ((array[mid] > key) ^ descendingOrder)
            return BinarySearch_Rec(array, descendingOrder, key, left, mid);
        else
            return BinarySearch_Rec(array, descendingOrder, key, mid + 1, right);
    }
    
    static int BinarySearch_Rec_Wrapper(int[] array, int key)
    {
        if (array.Length == 0)
            return -1;
    
        bool descendingOrder = array[0] > array[array.Length - 1];
        return BinarySearch_Rec(array, descendingOrder, key, 0, array.Length);
    }
    
    Итеративно:
    
    static int BinarySearch_Iter(int[] array, bool descendingOrder, int key)
    {
        int left = 0;
        int right = array.Length;
        int mid = 0;
    
        while (!(left >= right))
        {
            mid = left + (right - left) / 2;
    
            if (array[left] == key)
                return left;
    
            if (array[mid] == key)
            {
                if (mid == left + 1)
                    return mid;
                else
                    right = mid + 1;
            }
    
            else if ((array[mid] > key) ^ descendingOrder)
                right = mid;
            else
                left = mid + 1;
        }
    
        return -(1 + left);
    }
    
    static int BinarySearch_Iter_Wrapper(int[] array, int key)
    {
        if (array.Length == 0)
            return -1;
    
        bool descendingOrder = array[0] > array[array.Length - 1];
        return BinarySearch_Iter(array, descendingOrder, key);
    }
    


    Попытка №5


    Теперь нам нужно написать унифицированный алгоритм, который работает для любых направлений сортировок, и для поиска либо первого, либо последнего, либо любого элемента из дублирующих. Я не хочу повторять этот ужас, поэтому просто скопипастю то, что писал некоторое время назад:
    Вы правда хотите это видеть?
    Оно вам надо?
    Я вас предупреждал
    
    enum ElementToChoose
    {
    	First,
    	Last,
    	NoCare
    }
    
    /// <summary>
    /// Finds element equal to value in sorted array in range [low, high)
    /// </summary>
    static int binarySearch(int value, int[] array, bool ascendingOrder, ElementToChoose elementToChoose, int low, int high) {
    	// return valid invalid position
    	if (low >= high)
    		return -(low + 1);
    
    	// return first or last found element
    	if (elementToChoose == ElementToChoose.First)
    		if (value == array[low])
    			return low;
    
    	int last = high - 1;
    
    	if (elementToChoose == ElementToChoose.Last)
    		if (value == array[last])
    			return last;
    
    	int mid = low + (high - low) / 2;
    
    	// we have found some element
    	if (value == array[mid]) {
    		switch (elementToChoose) {
    			case ElementToChoose.NoCare:
    				return mid;
    
    			case ElementToChoose.First:
    				if (mid - low <= 1)
    					// array[mid] is the earliest element in array, return it
    					// because array[low] != value && array[low+1] == value, where mid == low + 1
    					return mid;
    				else
    					// try to find first element
    					// don't forget to capture current element {|0, 0|, 1} -> {0, 0}
    					return binarySearch(value, array, ascendingOrder, elementToChoose, low, mid + 1);
    			case ElementToChoose.Last:
    				if (last - mid <= 1)
    					// array[mid] is the last element in array, return it
    					// because array[last] != value && array[last - 1] == value, where mid == last - 1
    					return mid;
    				else
    					// try to find last element
    					// don't forget to capture current element {0, |0, 1|} -> {0, 1}
    					return binarySearch(value, array, ascendingOrder, elementToChoose, mid, high);
    		}
    	}
    
    	// choose left or right half, depending on sorting order & comparing value and mid
    	if ((value < array[mid]) ^ !ascendingOrder)
    		return binarySearch(value, array, ascendingOrder, elementToChoose, low, mid);
    	else
    		return binarySearch(value, array, ascendingOrder, elementToChoose, mid + 1, high);
    }
    

    Что плохого в этом коде, помимо того что он ужасен и комментарии написаны на непонятном языке? Этот код позволяет задуматься, а почему нельзя было написать 3 варианта поиска, а не городить малопонятного монстрика? Нет, если присмотреться, он вполне неплох, хотя и плох (если сравнить с другими версиями выше).

    Кстати, я сейчас подумал, что гораздо красивее представлять интервалы в виде объектов с волшебными свойствами/методами getFirstHalf, getSecondHalf (получают первую и вторую половину интервала), getStartPoint/getLastPoint (получают первую/последнюю точку интервала), increaseLength/decreaseLength (меняют длину интервала), moveStartPoint. Ну или еще какими-нибудь другими волшебными свойствами. Это чрезвычайно упростило бы понимание двоичного поиска, да и вообще любых алгоритмов.

    Бинарный поиск по монотонной функции
    Для того, чтобы написать алгоритм, нам нужно будет использовать числа с плавающей точкой. Плавающая точка… Если вы еще не произносите рефлекторно мат, когда слышите словосочетание «плавающая точка», значит вы плохо с ней работали. Давайте посмотрим код:

    
    // для нешарпистов - Func<float, float> функция, принимающая float и отдающая float
    static float BinarySearch_Func(Func<float, float> func, bool descendingOrder, float key, float left, float right)
    {
        float mid = (left + right) / 2;
    
        if (left == mid || mid == right)
            return mid;
    
        if ((func(mid) > key) ^ descendingOrder)
            return BinarySearch_Func(func, descendingOrder, key, left, mid);
        else
            return BinarySearch_Func(func, descendingOrder, key, mid, right);
    }
    
    static float BinarySearch_Func_Wrapper(Func<float, float> func, float key, float left, float right)
    {
        if (left > right)
            return float.NaN;
    
        bool descendingOrder = func(left) > func(right);
        bool isOk = true;
    
        if (!descendingOrder)
            isOk = func(left) <= key && key <= func(right);
        else
            isOk = func(right) <= key && key <= func(left);
    
        if (isOk)
            return BinarySearch_Func(func, descendingOrder, key, left, right);
        else
            return float.NaN;
    }
    

    Задайте себе несколько вопросов. Этот код работает? Почему он работает? Что за прикол с абсолютным сравнением float'ов? (если у вас не вызывает этот момент удивления, прошу читать статью Что нужно знать про арифметику с плавающей запятой?, возможно, найдете что-нибудь полезное).
    Хотите еще один клевый вопрос? Каков тип интервала left; right? Это [left, right], или [left, right), или (left, right], или (left, right)? Внимательно подумайте. Запустите этот кусок кода и подумайте еще раз:
    
    // Для нешарпистов x => x - лямбда-запись функции f(x) = x
    Console.WriteLine(BinarySearch_Func_Wrapper(x => x, 0.7f, 0.7f, 100.0f)); // Вывод: 0.7
    Console.WriteLine(BinarySearch_Func_Wrapper(x => x, 0.8f, 0.8f, 100.0f)); // Вывод: 0,8000001
    Console.WriteLine(BinarySearch_Func_Wrapper(x => x, 0.9f, 0.9f, 100.0f)); // Вывод: 0,9
    
    Console.WriteLine("{0:0.00000000}",0.8f); // Вывод: 0,80000000
    

    Итак, точка left у нас включается и исключается в зависимости от погоды на Марсе. Для точки right погода на Марсе тоже имеет важное значение (проверено). Т.е. мы складываем два числа a и b, делим сумму на два и получаем либо a, либо b, либо что-то между ними. Это забавно.
    На самом деле, эта фишка скорее всего прописана в стандарте, а может, вычисление mid зависит от опций компилятора/платформы. А может действительно от погоды на Марсе.

    Чтобы соблюсти хоть какой-то контракт, нам нужно в обертку поместить проверки func(left) == key и func(right) == key, тогда наши интервалы всегда будут закрытыми с обоих сторон.

    В качестве задачки, кому скучно будет: попытайтесь скрестить поиск по массиву с поиском по функции, покажите своего монстра.
    Те, кому не настолько скучно, могут показать хотя-бы альтернативные примеры реализаций бин. поиска, более красивые или с чуть-другими идеями.
    Те, кому очень-очень скучно, я предлагаю такую задачку: напишите бинарный поиск по функции, если все числа — рациональные, и представляются в виде несократимой дроби a/b. В качестве очень жестокого издевательства: числа a и b безграничные. Супер-сложность: все еще за O(lgn).

    Вообще, хочется спросить: а что все-таки лучше — одна монструозная функция, которая поддерживает выбор первого/последнего/любого из них или три функции, чрезвычайно похожих, но немного не таких?

    P.S: вполне возможно, что в моем коде есть ошибки. Буду благодарен, если укажите на них
    P.P.S: а какие комментарии должны быть к такому алгоритму?

    UPD1: Юзер fox_anthony предложил вместо -(1 + left) писать ~left. Подробнее: Оператор ~, msdn, c#
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 156
    • +8
      С бинарным поиском проблем не возникало. В свое время повозился с пирамидальной сортировкой и максимальным потоком.
      • +2
        Собственно, эта статья — описание типичнейших ошибок, которые могут допустить программисты при разработке и некоторые размышления о красоте коде, и попытках совместить красоту с корректностью алгоритма и его унифицированностью. Проблема в том, что не получается получить все вместе.
        • +6
          Так и надо было остановиться на 3 попытке, и не заниматься premature generalization, нет?
          Мне вообще непонятен смысл 4 попытки в аглоритме, возвращающем значение, а не индекс.
          • +1
            Хм? Возвращается индекс. Но первого из дублирующих элементов, а не первого, какой найдем. Только что проверил и для рекурсивного, и для итеративного прямым тестированием. вызов binarySearch_Array_Recursive_Wrapper(new int[] { 0,3,4,4,4,4,4,4,4,4,5 }, 4) выдает 2, т.е. 2-й элемент равен 4, раньше 4-к в массиве нет
            • 0
              Да, извиняюсь. В первых попытках было значение, в 4 проглядел
              • 0
                А есть ли в этом смысл — возвращать индекс именно первого из дублирующих элементов? Это специфика, которая мне в общем-то не пригодилась ни разу, даже для олимпиадных задач.
                • 0
                  Если потом потребуется перебирать все элементы, большие или равные искомого — то первый из дублирующих это то, что нужно. Аналогично, если потребуется перебирать строго большие — надо искать последний. Такое, например, используется в одном из вариантов слияния двух массивов без дополнительной памяти.
                  • 0
                    Ровно по этой причине поиск возвращает любой из равных. А кроме него есть lower/upperBound.
                    • 0
                      Интересно, каким образом авторы функций Search, LowerBound и UpperBound обошлись без нарушения принципа DRY.
                      • 0
                        См. этот комментарий. Ну это для lowerBound/upperBound. А бин. поиск который возвращает любой из равных может возвращать первый из равных.
          • 0
            Ну пирамидальная ещё ладно. А вот БДП с их красивым удалением меня какое-то время в тупик ставили:)
            • –2
              За последние полгода пришлось собеседовать 5 человек на должность веб-разработчика в нашу студию.

              Первое задание, на котором повалилось 4 человека: «Отсортируйте массив целых чисел по возрастанию. Метод сортировки любой. Язык программирования любой». Все вспомнили про пузырек, но:
              • 1 пытался писать использую только 1 условие (без циклов)
              • 2 пытались писать с использованием только 1 цикла и 1 условия (думаю все помнят что нужно 2 вложенных цикла и условие)
              • 1 сделал 2 вложенных цикла, но условие не внутри, а снаружи.


              Итого из 5 человек только 1 смог написать банальную сортировку пузырьком. А зарплатные ожидания у всех пятерых были огого!
              • +1
                А Вы публикуйте подобные работы. Для кого-то будет обучающим пособием(как не надо делать), а другим просто поднимет настроение…
                • +1
                  А нефиг пузырьком сортировать. Надо прямым перебором с созданием нового массива! Только хардор!

                  Хотя к комментарию есть вопрос — как можно написать сортировку без использования циклов? В чем там была суть идеи?

                  С 1 циклом еще боле-менее понятно. Так можно извратиться, в целом то. По крайне мере в голову приходит вариант с нахождением минимального значения в каждой итерации цикла и условии на перехват окончания цикла
                  • 0
                    Надо прямым перебором с созданием нового массива! Только хардор!

                    Если я вас правильно понял, то это отличная штука, при малом разбросе значений и большом количестве элементов :) O(n+m) вроде получается.
                    • +3
                      Именно так. Я посмотрел как оно правильно называется — сортировка подсчетом.
                    • 0
                      Подозреваю что первый сортировал 2 числа =о)
                      • 0
                        Вы совершенно правы, без циклов нельзя.
                        По факту очень многие начинающие программисты (а точнее те, кто не учил программирование а просто про него слышал) не понимают разницы между циклом и условием. Печально.
                        • +1
                          Рекурсивно :) В той же сортировке слиянием можно процедуру слияния описать через рекурсию и всё чудесно пишется без единого цикла.
                          • 0
                            Если используется оптимизация хвостовой рекурсии, то это по факту все-таки итеративный процесс, цикл
                          • 0
                            Метод любой, язык любой.
                            Dim arr() As Integer = {1, 2, 5, 6, 3, 8, 4, 9, 7} Dim result = From b In arr Order By b 'результат: 1,2,3,4,5,6,7,8,9
                            Без циклов и условий
                            • 0
                              Ну Вы же понимаете, что это жульничество.
                              • 0
                                Разве? Вот условие задачи: «Отсортируйте массив целых чисел по возрастанию. Метод сортировки любой. Язык программирования любой»
                                Язык: VB.NET
                                Метод: Linq запрос
                                Хотя Вы правы, надо было сразу SQL использовать.

                                ЗЫ.
                                Шутки ради (for fun) =0)
                          • НЛО прилетело и опубликовало эту надпись здесь
                            • +1
                              Вот у меня ощущение, что я бы тоже написал что-то вроде Collections.sort()
                              Потому что не вижу смысла в этой задаче ну никакого. Это даже не на логику про круглые люки.
                              • 0
                                Может быть у них веб-разработчики настолько суровы, что разрабатывают новый веб-ориентированный язык программирования.
                              • 0
                                Конечно. Но человек, который в состоянии написать пузырьки (пусть даже он описание идеи найдет в Интернете или получит на бумажке), лучше справится с задачами реальной жизни.
                          • +45
                            вы что, хотите писать программы без ошибок?
                            • +11
                              Я что, многого хочу?
                              • +22
                                Нет, этого очень легко достичь: просто не писать :)

                                «Не ошибается тот, кто ничего не делает» ©
                                • +2
                                  Ваши бы слова, да начальнику в уши…
                              • +5
                                Программа, написанная с «обычной» ошибкой и отсутствие программы (или программа типа return random();) — идентичные ситуации. Программа же, которая имеет критичную ошибку в редких случаях — гораздо опаснее.

                                Иногда человек говорит «я умею писать реализации алгоритма XYZ», но по факту такая реализация с багфиксингом может занять 2 недели брутто. Другой же человек говорит «я не умею писать XYZ», но по факту с гуглением и чтением док напишет за неделю.

                                Собственно, как мне показалось, статья призвана показать бессмысленность заявлений типа «X знает алгоритм Y» в реальной жизни.
                              • –7
                                >> int mid = left + (right — left) / 2; — как то сложновато
                                int mid = size >> 1;
                                читается попроще
                                • 0
                                  Тут ведь дело в чем, мы можем искать допустим в правой половине массива, тогда left = 10, right = 20 (к примеру), а mid уже будет равен 15, а не 5. Или вы что-то другое имели ввиду?
                                  • 0
                                    о нахождении половины в целом, конечно можно применить для поиска в отдельной части массива, но тогда уже оно сложнее)
                                • 0
                                  Вы всегда используется отрицания в случае, когда элемент не найден и нужно возвратить номер элемента для вставки.
                                  return -(1 + left);
                                  Но это неверно. Что будет в случае, когда нужно вернуть индекс 0? В таком случае будет неясно нашел ли Ваш алгоритм нужный элемент или выдал позицию, куда вставить текущий элемент.
                                  Для этой цели гораздо лучше подходит операция ~.
                                  • 0
                                    Если left = 0, тогда return — (1 + 0) = return -1. Все спец. индексы имеют отрицательное значение и смещение на 1.
                                    • 0
                                      Да, я понял, еще раз извиняюсь =)
                                      • 0
                                        Было дело писал интересную надстройку над классом List C# реализующий поиск первого и последнего элементав массиве при помощи бинарного поиска (например, в массиве 0 1 2 2 3 4 4 4 5 6 первый элемент равный 4 — 5, последний индекс элемента равного 4 — 7)
                                        using System;
                                        using System.Collections.Generic;
                                        using System.Text;
                                        
                                        namespace ObfuscatedNamespace
                                        {
                                            public class List<T> : System.Collections.Generic.List<T>
                                            {
                                                public List() : base() {}
                                                public List(IEnumerable<T> collection) : base(collection) { }
                                                public List(int capacity) : base(capacity) { }
                                        
                                                public int BinarySearchFirst(T item)
                                                {
                                                    return BinarySearchFirst(0, Count, item, null);
                                                }
                                        
                                                public int BinarySearchFirst(T item, IComparer<T> comparer)
                                                {
                                                    return BinarySearchFirst(0, Count, item, comparer);
                                                }
                                        
                                                public int BinarySearchFirst(int index, int count, T item, IComparer<T> comparer)
                                                {
                                                    if (index < 0 || count < 0) throw new ArgumentOutOfRangeException();
                                                    if (index + count > Count) throw new ArgumentException();
                                        
                                                    if (comparer == null)
                                                        comparer = Comparer<T>.Default;
                                        
                                                    if (comparer == null) throw new InvalidOperationException();
                                        
                                                    int low = index;
                                        
                                                    if (count == 0)
                                                        return ~index;
                                        
                                                    int middle;
                                        
                                                    int len = count;
                                                    int half;
                                        
                                                    while (len > 0)
                                                    {
                                                        half = len / 2;
                                                        middle = low + half;
                                        
                                                        if (comparer.Compare(this[middle], item) < 0)
                                                        {
                                                            low = middle + 1;
                                                            len = len - half - 1;
                                                        }
                                                        else
                                                            len = half;
                                                    }
                                        
                                                    if (low >= count || comparer.Compare(this[low], item) != 0)
                                                        return ~low;
                                                    else
                                                        return low;
                                                }
                                        
                                                public int BinarySearchLast(int index, int count, T item, IComparer<T> comparer)
                                                {
                                                    if (index < 0 || count < 0) throw new ArgumentOutOfRangeException();
                                                    if (index + count > Count) throw new ArgumentException();
                                        
                                                    if (comparer == null)
                                                        comparer = Comparer<T>.Default;
                                        
                                                    if (comparer == null) throw new InvalidOperationException();
                                        
                                                    int low = index;
                                        
                                                    if (count == 0)
                                                        return ~index;
                                        
                                                    int middle;
                                                    int r;
                                        
                                                    int len = count;
                                                    int half;
                                        
                                                    while (len > 0)
                                                    {
                                                        half = len / 2;
                                                        middle = low + half;
                                        
                                                        r = comparer.Compare(item, this[middle]);
                                        
                                                        if (r < 0)
                                                            len = half;
                                                        else
                                                        {
                                                            low = middle + 1;
                                                            len = len - half - 1;
                                                        }   
                                                    }
                                        
                                                    if (low > 0)
                                                    {
                                                        r = comparer.Compare(item, this[low - 1]);
                                                        if (r == 0)
                                                            return low - 1;
                                                        else
                                                            return ~low;
                                                    }
                                                    else
                                                        return ~low;
                                                }
                                        
                                                public int BinarySearchLast(T item)
                                                {
                                                    return BinarySearchLast(0, Count, item, null);
                                                }
                                        
                                                public int BinarySearchLast(T item, IComparer<T> comparer)
                                                {
                                                    return BinarySearchLast(0, Count, item, comparer);
                                                }
                                            }
                                        }
                                        

                                        Простите, что код без комментариев и описания. Может кому-то пригодится. Возможно кто-то укажет что можно сделать лучше =)
                                        • +2
                                          Появился новый тег — <spoiler>. Загляните в подсказку к форме комментирования.
                                          • +1
                                            Каюсь, простите, не так часто пишу комментарии…
                                          • 0
                                            Интересный подход. Т.е. вы представляете область поиска через начальную точку и его длину?
                                            • 0
                                              Да, через начальную точку и длину. Такие же параметры принимает функция BinarySearch оригинального класса System.Collections.Generic.List (от которого я собственно и породил новый List).
                                              Мне необходимо было пробегаться по определенной части массива элементов равных какому-то значению (например 4) причем в цикле и без операций сравнения на каждом шаге пробега (операции сравнения тяжеловесные, элементов в массиве много).
                                        • +4
                                          Извиняюсь, не досмотрел сразу =) Но в любом случае, лучше пишите:
                                          return ~left;
                                          

                                          вместо
                                          return -(1+left);
                                          

                                          • +2
                                            Век живи — век учись, сейчас добавлю апдейтом в пост.
                                            • +1
                                              Опасные это игрушки. В любом случае не помешает написать комментарий:
                                              return ~left; // -(1+left); premature optimization
                                              • +2
                                                Чем строчку кода, которая поясняет строчку кода — лучше уж оставить старую версию…
                                                • 0
                                                  Согласен, — это самое лучшее решение. По крайней мере, если ставить перед собой цель изложить алгоритм.
                                                  • 0
                                                    Но ведь операция ~ естественным образом отражает отрицательные числа в неотрицатальные и наоборот. Причем сопоставления однозначное с обоих сторон.
                                                    • –1
                                                      Естественный для человека — это "- variable", а хак с битовыми операциями лучше оставить компилятору, ему видней, как на этой платформе записываются целые положительные и отрицательные числа.
                                          • +18
                                            Исходя из статьи я так и не понял, почему вы не можете написать бинарный поиск — вы его написали. И я бы не сказал, что путь был труден и тернист. Любая вещь сложнее 2 + 2 так и пишется. Сначала скелет, затем учёт нюансов и правка багов. Часть из последних может вылезти в дальнейшем. Их число будет меньше, если есть опыт в этой области, а мозг трезв :)

                                            Что действительно вынесло мне мозг с корнями пару лет назад, так это динамика по изломанному профилю. Или мне не удалось найти внятного материала, или это страшно сложная штука.
                                            • 0
                                              Ну это довольно желтый заголовок, но, вообще, я так и не понял, как правильно и красиво объединить бинарный поиск по массиву (целочисленные индексы) с бинарным поиском по функции (индексы с плавающей погрешностью, сама функция тоже с плавающей погрешностью). Ну и при этом хотелось получить некоего монстра, который может все, и выбирать первый элемент из дубликатов, и последний, и сам определять направление сортировки и при этом корректно работать на определенных интервалах.
                                              • +5
                                                прежде чем делать монстра, который делает все — сделайте монстра, который хорошо сделает то что нужно. Это одна из главных проблем — пытаться сразу все учесть.
                                                • +2
                                                  Так я постепенно делаю, шаг за шагом, а потом все внезапно становится страшно, некрасиво и иногда непонятно. С идеей делать все постепенно я уже свыкся.
                                                • 0
                                                  А зачем Вам такой монстр? Хотите написать функцию «сделать хорошо»? Все таки алгоритмы должны быть под конкретную задачу, а не на все случаи жизни. Сегодня проскакивал опрос про то, сколько бесполезного кода пишет программист.
                                                  • 0
                                                    Ну этот код я писал для тренировки, чтобы понять как писать, какие баги могут возникнуть
                                                • +2
                                                  Не хватает юнит тестов.
                                                  • 0
                                                    Динамика по изломанному профилю — очень частная штука. Общая идея — сделаем профиль не прямым, а фигуристым. Из-за этого, естественно, меняется мощность профиля, функция переходов да и вообще логика. Но может получиться так, что общая асимптотика будет заметно лучше, чем при прямом профиле… Какая форма у фигуристого профиля и какие параметры этой формы — сильно зависит от задачи. В общем, штука не столько сложная, сколько очень частная и вполне можно было не найти внятного материала, ага…

                                                    Гугл, кстати, сходу выдает отличный пример: informatics.mccme.ru/moodle/mod/book/view.php?id=290&chapterid=78
                                                  • +23
                                                    Автор ищет красивый код, а функции именует, смешав все стили…
                                                    • +2
                                                      Да, по поводу именования. В оригинале (в исходном коде, который я писал) функции вообще назывались как binarySearch_Func_Recursive_Wrapper. Просто тут я придерживаюсь подхода, что если что-то в названии определяет способ действия или к чему прикладывается действие, то это нужно отделять несколько по другому. В реальности я бы написал private binarySearch() — собственно функция, и public binarySearch — функция-обертка.
                                                      • +3
                                                        Но все-таки в C# CamelCase, поэтому лучше BinarySearch.
                                                        • 0
                                                          Спасибо за совет, просто еще не привык к стилю наименованию, все норовит к более удобному вернуть
                                                          • +5
                                                            То, что вы написали — FirstCaps, camelCase выглядит так.
                                                            • 0
                                                              Хотя то, чему меня учили и мнение википедии отличаются
                                                              • 0
                                                                Все-таки не соглашусь.

                                                                Позволю уточнить, что я имел ввиду UpperCamelCase.
                                                        • –5
                                                                      int[] a = { 1, 3, 4, 6, 8, 4, 7, 8, 2, 3, 6, 1 };
                                                          
                                                                      Action<int, int> f = null;
                                                                      f = delegate (int L, int R)
                                                                      {
                                                                          if (R - L == 1) return;
                                                          
                                                                          int pilot = a[L]; // (L+R)/2 заметно осложняет анализ. Если у нас есть предположение, что числа случайные, то никаких преимуществ одного перед другим нет.
                                                                          int l = L, r = R;
                                                          
                                                                          // примем что для всех a[L..l) < pilot и a[r..R) >= pilot . Это условие должно выполняться на входе в цикл, по окончании каждой итерации, и на выходе из цикла.
                                                                          // на каждой итерации должно происходить только одно из трёх: либо уменьшаться r , либо увеличиваться l, либо происходить обмен.
                                                          
                                                                          while (l != r) // только хардкор! никаких l <= r. 
                                                                              if (a[l] < pilot) l++;
                                                                              else if (a[r-1] >= pilot) r--;
                                                                              else
                                                                              {
                                                                                  int t = a[l]; a[l] = a[r-1]; a[r-1] = t;
                                                                              }
                                                          
                                                                          if (a[L] == pilot) // если pilot остался на своём месте, то pilot -- наименьший элемент во всём a[L,R). Просто пропускаем. Это тот самый случай вырождения в O(NN)
                                                                              f(L + 1, R);
                                                                          else
                                                                          { // помним, что после выхода из цикла l и r не менялись, следовательно, всё ещё l == r, все условия корректности выполняются
                                                                              f(L, l);
                                                                              f(r, R);
                                                                          }
                                                                      };
                                                                      f(0, a.Length );
                                                          
                                                                      foreach(var e in a)          System.Console.WriteLine(e);
                                                          • +3
                                                            Извините, но то что у вас — это линейный поиск, кроме того, чрезвычайно запутанный. В статье же описывается бинарный поиск, для отсортированного массива. Он работает с асимптотикой O(lgn), т.е. время работы пропорционально логарифму n. Время работы линейного поиска пропорционально самому числу n (размеру массива).
                                                            • +1
                                                              ой, точно, статья-то про поиск :)
                                                              я сортировку написал. quicksort. извиняюсь :)
                                                              • +2
                                                                Я прочитал ваш код по диагонали и не заметил, что он сортирует массив :-)
                                                          • –1
                                                            Можно вызвать стандартную функцию: msdn.microsoft.com/en-us/library/w0k41tbs%28v=vs.71%29.aspx
                                                            • +9
                                                              Зачем так сложно-то?!
                                                              Функция, которая возвращает позицию элемента, значение которого равно х, в векторе v[], можно задать левую и правую границу поиска:

                                                              // Pre: (0 <= left) and (right < v.size()) and (v is sorted in an ascending order)
                                                              // Post: returns a number i, left<=i<=right and v[i]==x.
                                                              //		 If there is no element x in v[], returns -1.
                                                              int position(double x, const vector<double>& v, int left, int right) {
                                                                  if (left > right) return -1;
                                                                  int pos = (left + right)/2; // the middle of v[left,right]
                                                                  if (x < v[pos]) return position(x, v, left, pos - 1);
                                                                  if (x > v[pos]) return position(x, v, pos + 1, right);
                                                                  return pos;
                                                              }
                                                              
                                                              • 0
                                                                P.S. Используется алгоритм бинарного поиска, конечно же
                                                                • –3
                                                                  Ваш метод теряет инфу (например, то, что вы возвращаете -1, а не ~left, не дает использовать функцию для поиска, куда нужно вставить определенный элемент), ваш метод работает только для одного направления сортировки, возвращает любой элемент, а не самый первый из дубликатов. Почитайте статью — куча кода написана не просто так.
                                                                  • +11
                                                                    А если сортировка была не по возрастанию или убыванию, а по отклонению от среднего элемента?
                                                                    Ваш код этого тоже не предусматривает!

                                                                    Хотите универсальности — смотрите на стандартные библиотеки. Считается, что элементы отсортированы по возрастанию в соответствии с переданной функцией сравнения. По умолчанию функция сравнения — оператор < для соответствующего типа.

                                                                    Если пользователь отсортировал с одной функцией сравнения, а ищет с другой — то он сам себе злобный буратино.
                                                                    • +2
                                                                      Спасибо за замечание по поводу функций сравнения, протупил как-то
                                                                • +7
                                                                  пыхпых
                                                                  • 0
                                                                    пардон, ctrl-enter случайно нажал. Продолжение коммента:
                                                                    	function bsearch($hs, $nee) {
                                                                    		$i1 = 0;
                                                                    		$i2 = count($hs);
                                                                    
                                                                    		do {
                                                                    			$i = floor(($i1 + $i2) / 2);
                                                                    			if ($hs[$i] == $nee) return $i;
                                                                    			if ($hs[$i] < $nee) $i1 = $i;
                                                                    			else $i2 = $i;
                                                                    		} while($i2 - $i1 > 1 || $i1 != $i);
                                                                    		
                                                                    		return -1;
                                                                    	}
                                                                    
                                                                    
                                                                    • 0
                                                                      Еще вариант (немного компактнее + с учетом взятия минимального индекса из одинаковых и возврата ближайшего:
                                                                      	function bsearch_nearest($hs, $nee) {
                                                                      		for ($i1 = 0, $i2 = count($hs), $i = -1; $i2 - $i1 > 1 || $i1 != $i; ) {
                                                                      			$i = floor(($i1 + $i2) / 2);
                                                                      			if ($hs[$i] == $nee) return $i;
                                                                      			$hs[$i] < $nee? ($i1 = $i): ($i2 = $i);
                                                                      		}
                                                                      		return $i;
                                                                      	}
                                                                      	
                                                                      	function bsearch($hs, $nee) {
                                                                      		$i = bsearch_nearest($hs, $nee);
                                                                      		while($i > 0 && $hs[$i - 1] == $nee) $i--; //return lowest index if there are few matching
                                                                      		return array(($hs[$i] == $nee? $i: -1), $i); //returns array: [0] => lowest matching index (or -1); [1] => nearest index
                                                                      	}
                                                                      
                                                                    • НЛО прилетело и опубликовало эту надпись здесь
                                                                      • +2
                                                                        Ну у нас печальный универ, как и вся страна впрочем :-)(. Украина, Харьков, ХИРЭ.
                                                                        У нас будет предмет «Алгоритми та структури даних» на втором курсе, т.е. сразу после лета, но на ОДИН семестр. За гуманитарной и общеобразовательной ерунды у нас много. К примеру, у нас будет два семестра философии. Ну это если верить плану, который у нас кривой.
                                                                        • НЛО прилетело и опубликовало эту надпись здесь
                                                                          • 0
                                                                            Ну, для начала, я даже не знаю, точно ли всего лишь один семестр и каков будет преподаватель. Поживем — увидим, а пока буду читать и прорабатывать книжки
                                                                      • 0
                                                                        Насчёт возвращения первого/последнего из равных значений. В отсортированном массиве они всегда будут идти по порядку. Так почему бы не идти влево/вправо от найденного элемента, пока не наткнёмся на последнее равное значение:

                                                                        if (type == last)
                                                                        while (arr[n++] == value);
                                                                        else
                                                                        while (arr[n--] == value);
                                                                        return n;

                                                                        • +2
                                                                          Вот вам пример массива: 1 число 5, потом идет 10^9 чисел 8, потом идет число 9. Нужно найти первое вхождение числа 8. Прикиньте, сколько займет поиск
                                                                          • 0
                                                                            И тем самым вы переключаетесь с бинарного поиска в линейный!
                                                                            А нужно всего лишь продолжать итерации бинарного поиска, но чуть поменять условие (искать не просто совпадение, а вдобавок НЕсовпадение предыдущего элемента).
                                                                          • +1
                                                                            Обычно, если функция может не увенчаться успехом, и нужно как-то уведомить об этом пользователя, а может, выкинуть исключение, то пишут 2 варианта функции:

                                                                            static bool TryBinarySearch_Iter(int[] array, int key, out int index)
                                                                            {
                                                                            }

                                                                            /// <exception cref=«KeyNotFoundException»/>
                                                                            static int BinarySearch_Iter(int[] array, int key)
                                                                            {
                                                                            int result;
                                                                            if (!TryBinarySearch_Iter(array, key, out result))
                                                                            throw new KeyNotFoundException();
                                                                            return result;
                                                                            }
                                                                            • +12
                                                                              Если вам интересно, как это обычно делают на олимпиадах про программированию.
                                                                              1. Никому не надо искать первый элемент из одинаковых. Это упрощает алгоритм.
                                                                              2. Направление убывания/возрастания известно в 90% случаев. А если не известно, то обычно все и еще хуже.
                                                                              3. Рассматриваются 2 а не 3 случая.
                                                                              Получается следующее:
                                                                              int[] data;
                                                                              int getIndex(int left, int right, int x) {
                                                                                while (right-left>1) {
                                                                                  int middle=(left+right)/2; // обычно не нужно больше 10^9 элементов.
                                                                                  if (data[middle]>=x) {
                                                                                    left=middle;
                                                                                  } else {
                                                                                    right=middle;
                                                                                  }
                                                                                }
                                                                                return left;
                                                                              }
                                                                              

                                                                              Дальше тот, кто использует эту функцию может проверить найден x или отрезок [data[result], data[result+1]) которому он принадлежит сравнив data[result] и x. Ну и на него же ложатся обязанности проверить data[left]<=x, x<data[right]. Обычно используется left=0, right = data.length, а data[0]<=x следует из условия задачи. А если не следует, часто имеет смысл добавить фиктивный элемент.

                                                                              Достоинства такого подхода — короче уже некуда и очень трудно в нем ошибиться. Достаточно понимать, что инвариант алгоритма это data[left]<=x<data[right]. Плюс можно использовать right=data.length, хотя такого элемента в массиве нет. Он предполагается равным +бесконечности.
                                                                              • 0
                                                                                Спасибо за информацию
                                                                              • +4
                                                                                > а что все-таки лучше — одна монструозная функция, которая поддерживает выбор первого/последнего/любого из них или три функции, чрезвычайно похожих, но немного не таких?

                                                                                Лучше набор функций, каждая из которых делает одну простую задачу, но их можно комбинировать как кубики лего и создавать что-то более сложное. Такие функции проще читать и тестировать.

                                                                                Как пример такого подхода здесь (с натяжкой):
                                                                                * Чтобы найти последнее вхождение, можно перевернуть массив и искать первое.
                                                                                * Поиск по массиву можно представить как поиск по функции. Функция в качестве Y возвращает элемент массива по индексу int(X). Если X меньше 0, или больше длины массива, тогда возвращаем минус бесконечность или бесконечность.

                                                                                Но конечно лучше не морочить себе голову и написать 2 отдельных поиска, для массивов и функций. Тем более что для функций алгоритм будет очень отличаться, потому что начальные значения left и right могут быть неизвестны, и функция поиска сама должна их найти примерно таким способом. И вообще для монотонных функций лучше подходит метод секущих, он быстрее сходится.
                                                                                • 0
                                                                                  Переворачивание массива не пойдет по причине увеличения сложности алгоритма.
                                                                                  • 0
                                                                                    Не совсем понял, вычислительной сложности (big O), или сложности реализации bin_search?

                                                                                    Вот пример на Python как можно избежать и того и другого (хотя изврат еще тот):

                                                                                    from bisect import bisect_left
                                                                                    
                                                                                    # our default binary search based on bisect_left() from stdlib
                                                                                    def bin_search_left(a, x):
                                                                                        i = bisect_left(a, x)
                                                                                        if i != len(a) and a[i] == x:
                                                                                            return i
                                                                                        raise ValueError
                                                                                    
                                                                                    # reverse list in O(1): [1, 2, 3] -> [-3, -2, -1]
                                                                                    class RevList():
                                                                                        def __init__(self, list):   self.list = list
                                                                                        def __len__(self):          return len(self.list)
                                                                                        def __getitem__(self, key): return -self.list[len(self.list) - key - 1]
                                                                                    
                                                                                    # rightmost occurrence in terms of bin_search_left
                                                                                    def bin_search_right(a, x):
                                                                                        return len(a) - 1 - bin_search_left(RevList(a), -x)
                                                                                    
                                                                                    # and action!
                                                                                    arr = [2, 3, 5, 5, 5, 7, 11]
                                                                                    print bin_search_left(arr,  5) # 2
                                                                                    print bin_search_right(arr, 5) # 4
                                                                                    
                                                                                    • 0
                                                                                      self.list[len(self.list) - key - 1]
                                                                                      

                                                                                      если что, то можно просто
                                                                                      self.list[- key - 1]
                                                                                      


                                                                                      • 0
                                                                                        Ага, не заметил. Твой вариант еще лучше тем, что поддерживает отрицательные значения key.
                                                                                • +1
                                                                                  Спасибо за статью — очень понравилась! Примечательно, что большинство критиков приводят в пример намного худший код, если характеризовать его по признакам корректности, универсальности и читаемости.
                                                                                  • +2
                                                                                    А когда мне надо было написать, я взял у Кнута самый простой вариант и реализовал так (python):
                                                                                    # coding: utf-8
                                                                                    
                                                                                    class Element:
                                                                                        def __init__(self, key, value):
                                                                                            self.key = key
                                                                                            self.value = value
                                                                                    
                                                                                        def __str__(self):
                                                                                            return "%d (%s)" % (self.key, self.value)
                                                                                    
                                                                                    # Обычный бинарный поиск
                                                                                    def BinSearch(arr, elem, l, u):
                                                                                        if not arr:
                                                                                            return -1
                                                                                    
                                                                                        while True:
                                                                                            if u < l:
                                                                                                return -1
                                                                                            i = (l + u) / 2
                                                                                            if elem.key < arr[i].key:
                                                                                                u = i - 1
                                                                                            elif elem.key > arr[i].key:
                                                                                                l = i + 1
                                                                                            else:
                                                                                                return i
                                                                                    
                                                                                    array = [Element(key, chr((key % 26) + 65,) ) for key in [1, 7, 11, 12, 24, 123]]
                                                                                    key = 12
                                                                                    
                                                                                    print "array =", map(str, array)
                                                                                    print "key = %d" % key
                                                                                    print "index =", BinSearch(array, Element(key, "value"), 0, len(array) - 1)
                                                                                    
                                                                                    raw_input("Press any key...")
                                                                                    


                                                                                    Вывод:
                                                                                    array = ['1 (B)', '7 (H)', '11 (L)', '12 (M)', '24 (Y)', '123 (T)']
                                                                                    key = 12
                                                                                    index = 3
                                                                                    Press any key...
                                                                                    
                                                                                    • +2
                                                                                      А почему нельзя использовать upper_bound и lower_bound? (кроме желания написать один алгоритм для решения всех задач, конечно) У них нет проблемы с тем, какой индекс вернуть. Они оставляют информацию о поиске, если используются для дальнейшей вставки элемента… Я что-то упускаю?
                                                                                      • 0
                                                                                        Мне прислали в личку решение с помощью операций lower_bound и upper_bound + объяснили их реализацию. Да, красиво.
                                                                                        • +1
                                                                                          По вашей просьбе размещаю и здесь:
                                                                                          осторожно, много текста
                                                                                          Давайте попробуем искать не первый/последний из эквивалентных элементов, а границы содержащего их интервала.

                                                                                          Интервал будет полуоткрытый справа, т.е. [lower_bound, upper_bound) как и все используемые интервалы. В случае, если искомого элемента нет, интервал будет пустой и обе границы (у пустого интервала границы равны) будут указывать на «место для вставки».

                                                                                          Для определения как отсортирована последовательность используем компаратор.
                                                                                          Будем считать, что компаратор comp в нашей последовательности выполняет роль оператора < и элементы в ней отсортированы по возрастанию (возрастанию относительно компаратора).
                                                                                          Т.е. если у нас последовательность целых чисел отсортирована по убыванию, то компаратором в ней будет оператор >. Если у нас последовательность пар чисел, отсортированных по величине второго числа… ну вы поняли о чем я.

                                                                                          lower_bound — позиция первого элемента, который не меньше искомого.
                                                                                          upper_bound — позиция первого элемента, который больше искомого.

                                                                                          Я буду использовать не индексы, а итераторы т.к. считаю, что в данной постановке задачи они уместнее (а ещё потому, что я это буду делать на C++ «в стиле STL»).

                                                                                          Попробуем найти lower_bound:

                                                                                          template<typename FwdIter, typename T, typename Comp>
                                                                                          FwdIter lower_bound(FwdIter first, FwdIter last, T const& x, Comp comp)
                                                                                          {
                                                                                              // если интервал пустой, то его и возвращаем
                                                                                              if (first == last)
                                                                                                  return first;
                                                                                              
                                                                                              // вычислим позицию среднего элемента
                                                                                              FwdIter middle = first;
                                                                                              std::advance(middle, std::distance(first, last) / 2);
                                                                                              
                                                                                              // Если средний элемент меньше искомого, т.е. искомый больше среднего элемента,
                                                                                              // то т.к. последовательность отсортирована по возрастанию,
                                                                                              // искомый элемент должен находиться справа от среднего, иначе — слева
                                                                                              if (comp(*middle, x))
                                                                                                  return lower_bound(++middle, last, x, comp);
                                                                                              else
                                                                                                  return lower_bound(first, middle, x, comp);
                                                                                          }
                                                                                          


                                                                                          upper_bound можно выразить через lower_bound:
                                                                                          У нас есть оператор <, а нам нужен ≤.
                                                                                          Выразим одно через другое:
                                                                                          a ≤ b ⇔ !(b < a)

                                                                                          template<typename FwdIter, typename T, typename Comp>
                                                                                          FwdIter upper_bound(FwdIter first, FwdIter last, T const& x, Comp comp)
                                                                                          {
                                                                                              typedef typename std::iterator_traits<FwdIter>::value_type value_type;
                                                                                              
                                                                                              auto less_equal = [&comp](value_type const& a, T const& b){return !comp(b, a);};
                                                                                              
                                                                                              return lower_bound(first,last, x, less_equal);
                                                                                          }
                                                                                          


                                                                                          Варианты для компаратора по умолчанию пишутся тривиально.

                                                                                          Ну и осталась обертка для проверки входит ли элемент в последовательность и на какой позиции.

                                                                                          template<typename FwdIter, typename T, typename Comp>
                                                                                          FwdIter binary_search(FwdIter first, FwdIter last, T const& x, Comp comp)
                                                                                          {
                                                                                              FwdIter found = lower_bound(first, last, x, comp);
                                                                                             
                                                                                              // Если элемент не найден, found может оказаться равен правой границе.
                                                                                              // Если found указывает на существующий элемент, то он не меньше искомого.
                                                                                              // Т.е. *found или больше или равен x, если больше, то x не нашелся.
                                                                                              if (found == last || comp(x, *found))
                                                                                              {
                                                                                                  // Элемент не найден.
                                                                                                  // Вернем верхнюю границу диапазона в качестве индикатора.
                                                                                                  return last;
                                                                                              }
                                                                                             
                                                                                              return found;
                                                                                          }
                                                                                          


                                                                                          Последняя обертка, не даёт информацию о месте вставки, если элемент не нашелся, однако никто не запрещает воспользоваться lower_bound напрямую, если мы собираемся вставлять элемент.

                                                                                          За исключеним нескольких нюансов, мы практически переизобрели соответствующие алгоритмы из STL:
                                                                                          lower_bound
                                                                                          upper_bound
                                                                                          binary_search
                                                                                          equal_range

                                                                                          Тщательно не тестировал, но вроде работает.
                                                                                      • +2
                                                                                        Капец. Столько комментариев, и до сих пор никто не дал простого совета: «попробуйте написать этот алгоритм через тесты». Каждый тест, по сути, и является записанным примером использования функции. Можно начинать с самых тривиальных примеров, чтобы создать интерфейс функции и базовый алгоритм работы, а затем, добавляя «неприятные» примеры один за другим, добиться корректной работы на граничных условиях.

                                                                                        Чистить код тоже намного проще, если он покрыт тестами. Надо просто прогонять их после каждого небольшого рефакторинга. Тогда сразу будет видно, что в логике ничего не сломалось.
                                                                                        • 0
                                                                                          Тесты наше все, если речь идет о примитивных алгоритмах вроде добавления лайка в базу. Но если задача не тривиальная, нужно сначала хорошо подумать и понять как ты ее будешь решать в принципе, а потом уже фигачить тесты.

                                                                                          Словами Питера Норвига:
                                                                                          «You can test all you want and if you don’t know how to approach the problem, you’re not going to get a solution.»

                                                                                          «Можно тестировать сколько угодно, но если ты не знаешь как подойти к проблеме, ты ничего этим не добьешься».

                                                                                          Вот классический пример (англ.) Один чувак (гуру тестирования), нафигачил тестов, но так как он тупо не знает как решить проблему в принципе, не сдвинулся с мертвой точки. Другой без всяких тестов сходу сел и написал красивейший код.

                                                                                          • 0
                                                                                            Не понимаю, что Вы нашли нетривиального в алгоритме двоичного поиска. В списке кат, предназначенных для отработки навыков TDD, есть задачи куда сложнее.
                                                                                            • +1
                                                                                              Абсолютно тривиальный алгоритм. Но вот из Кнута: хотя первый двоичный поиск был опубликован в 1946 году, первый двоичный поиск не содержащий ошибок был опубликован только в 1962.

                                                                                              И в продолжение — ошибка в реализации из Java, которая оставалась незамеченной 10 лет. Умиляет апдейт 2008 года, когда они нашли еще одну ошибку.
                                                                                              • +1
                                                                                                Так это ещё два аргумента в пользу использования TDD на этой задаче :)

                                                                                                В книге «Идеальный код» как раз есть статья Альберто Савойи «Красивые тесты», где разбирается тестирование (барабанная дробь...) двоичного поиска! В ней приводятся те же самые факты (Кнут & Бентли) в качестве аргументов к утверждению, что без тестов реализовать этот алгоритм правильно далеко не просто.

                                                                                                А далее подробно разбирается, как реализовать этот алгоритм, тестируя через JUnit. Найдите и почитайте статью. Рекомендую!
                                                                                              • 0
                                                                                                По ссылке хорошие задачи, но тоже все тривиальные. Разве что в покере важно правильно выбрать представление рейтинга.
                                                                                          • 0
                                                                                            Всю статью не осилил.
                                                                                            Есть бинарный входящий в стандартный stl на плюсах:
                                                                                            binary seach
                                                                                            lower bound
                                                                                            Как я понимаю — нужно для обычных массивов, поэтому заменить итераторы на указатели, остальное вроде не сложно немного переделать.
                                                                                            • +1
                                                                                              Либо «Я некрофил и я недавно прочёл статью двухлетней давности», либо блог надо бы выбрать личный или Q&A.

                                                                                              Почему? Потому, что никаких выводов, никаких заключений. Морали — и той нету. Есть только вопрос «правильно ли я сваял функцию?»
                                                                                              • +3
                                                                                                Купите себе замечательную книгу Кормена «Алгоритмы: построение и анализ». Там всё достаточно внятно описано, очень советую.
                                                                                                • 0
                                                                                                  присоединяюсь к рекомендации.
                                                                                                • +4
                                                                                                  Такие тривиальные вещи идеально «разгрызаются» через TDD. Задача не использует внешних ресурсов…. Эх, где мои 17 лет (читай 16-22)? Попробуйте и достигните нирваны.
                                                                                                  • 0
                                                                                                    Для целочисленного массива получилось так:
                                                                                                            static int BinSearch(int[] m,int a,int kf) {
                                                                                                                int len=m.Length;
                                                                                                                int cf=0;
                                                                                                                if(len==0) return -1;
                                                                                                                if(m[0]>m[len-1]) {
                                                                                                                    a=~a; cf=-1;
                                                                                                                }
                                                                                                                int x1=-1,x2=len;
                                                                                                                while(x2-x1>1) {
                                                                                                                    int x3=x1+(x2-x1)/2;
                                                                                                                    int h=m[x3]^cf;
                                                                                                                    if(h==a && kf==0) return x3;
                                                                                                                    if(kf<0 ? h>=a : h>a) x2=x3;
                                                                                                                    else x1=x3;
                                                                                                                }
                                                                                                                if(kf<0) {
                                                                                                                    if(x2<len && (m[x2]^cf)==a) return x2;
                                                                                                                } else {
                                                                                                                    if(x1>=0 && (m[x1]^cf)==a) return x1;
                                                                                                                }
                                                                                                                return ~x2;
                                                                                                            }
                                                                                                    
                                                                                                    

                                                                                                    kf=-1 для первого элемента, 0 для любого, 1 для последнего.
                                                                                                    Вроде бы, все учтено, поймать не удалось.
                                                                                                    • 0
                                                                                                      А с произвольным сравнением еще проще — 19 строк:

                                                                                                              static int BinSearch(int[] m,int a,int kf,Comparison<int>cmp) {
                                                                                                                  int len=m.Length;
                                                                                                                  if(len==0) return -1;
                                                                                                                  int cf=cmp(m[0],m[len-1])<=0 ? 1 : -1;
                                                                                                                  int x1=-1,x2=len;
                                                                                                                  while(x2-x1>1) {
                                                                                                                      int x3=x1+(x2-x1)/2;
                                                                                                                      int h=cf*cmp(m[x3],a);
                                                                                                                      if(h==0 && kf==0) return x3;
                                                                                                                      if(kf<0 ? h>=0 : h>0) x2=x3;
                                                                                                                      else x1=x3;
                                                                                                                  }
                                                                                                                  if(kf<0) {
                                                                                                                      if(x2<len && cmp(m[x2],a)==0) return x2;
                                                                                                                  } else {
                                                                                                                      if(x1>=0 && cmp(m[x1],a)==0) return x1;
                                                                                                                  }
                                                                                                                  return ~x2;
                                                                                                              }
                                                                                                      

                                                                                                      • 0
                                                                                                        а если все \r\n удалить?
                                                                                                        • 0
                                                                                                          Тогда будет неудобно читать.
                                                                                                          • 0
                                                                                                            Так уже. Вы же целеноправленно строки сокращаете :):

                                                                                                            1. «thin return» на одной строке
                                                                                                            2. Несколько переменных объявлено вместе
                                                                                                            3. «kf<0? h>=0: h>0» — конфета
                                                                                                            4. А где пробелы между логическими блоками? Я бы поставил минимум в трех местах.
                                                                                                            • 0
                                                                                                              Ну, не знаю. Я так привык. В каждой строчке по одному оператору. Все строки достаточно короткие.

                                                                                                              Возражения про «kf<0? h>=0: h>0» не понял вообще — нормальное условие, как мне кажется. «Пробелы между логическими блоками» — что имеется в виду?
                                                                                                              • 0
                                                                                                                Я имел ввиду пустые строки отделяющие логические блоки кода. Здесь я бы поставил перед while, последним внешним if и return.

                                                                                                                «kf<0? h>=0: h>0» не уверен :), но помоему он определяет в какую сторону идти в зависимости от направления отсортированности масива-параметра. Вобщем, без поллитра…

                                                                                                                Может я и не прав, и вы код не уплотняли. Возможно, дело вкуса. Возможно, виноваты имена переменных. Но читать очень тяжело. Как результат — закрались сомнения :).
                                                                                                                • 0
                                                                                                                  Нет, условие «kf<0? h>=0: h>0» определяет, какой конец отрезка из элементов, равных искомому, мы ищем — левый или правый. Направление отсортированности находится в переменной cf и используется в строчке «int h=cf*cmp(m[x3],a);»

                                                                                                                  А если бы я уплотнял строки, то:
                                                                                                                  — описал бы все три переменных x1,x2,cf в одной строке (нехорошо, поскольку в одну инициализацию попадают переменные разной семантической окраски. С x1, x2 такой проблемы нет — они оба индексы в массиве);
                                                                                                                  — поставил бы фигурные скобки в конец предыдущих строк (выигрыш 2 или 3 строк, но я так не люблю читать);
                                                                                                                  — поставил бы последний if сразу после else и убрал фигурные скобки. По моим критериям, в этом нет никакого криминала, но нарушается симметрия фрагмента программы.
                                                                                                    • 0
                                                                                                      Вообще у вас все варианты какие-то странные. Я вот в упор не понимаю, зачем вносить проверку на равенство в цикл, достаточно одной проверки на неравенство в цикле и одной проверки — вне его, это будет значительно эффективнее. Когда ковырял двоичный поиск под CUDA, написал следующее:

                                                                                                      Скрытый текст
                                                                                                      			unsigned int left = 0, right = hashlist_count;
                                                                                                      
                                                                                                      			// now binary search
                                                                                                      			while (left < right)
                                                                                                      			{
                                                                                                      				unsigned int middle = left + (right - left) / 2;
                                                                                                      				
                                                                                                      				if (a <  hashlist[2*middle] ||
                                                                                                      					a == hashlist[2*middle] && b <= hashlist[2*middle+1])
                                                                                                      				{
                                                                                                      					right = middle;
                                                                                                      				}
                                                                                                      				else
                                                                                                      				{
                                                                                                      					left = middle + 1;
                                                                                                      				}			
                                                                                                      			}
                                                                                                      
                                                                                                      			if (a == hashlist[2*right] && b == hashlist[2*right+1])
                                                                                                      			{
                                                                                                      				// matched!
                                                                                                      				unsigned int add = 1 << (output_index % 32);
                                                                                                      				atomicAdd(&(((unsigned int*)match_out)[output_index / 32]), add);
                                                                                                      			}
                                                                                                      



                                                                                                      Хотя, это тоже специфика, CUDA «не любит» лишние ветвления.
                                                                                                      На hashlist[2*x] не обращайте особого внимания, просто разбил 64-битные числа на 2 по 32 бита (так быстрее, но сравнивать нужно каждую «половинку»).
                                                                                                      • 0
                                                                                                        Да, пардон, с кодом погорячился:

                                                                                                        В моем примере мы ищем пару (a:b) в массиве вида hashlist[2*n], отсюда такие хитрые условия. Не будь этого было бы достаточно (ищем x):
                                                                                                        unsigned int left = 0, right = hashlist_count;
                                                                                                        
                                                                                                                    // now binary search
                                                                                                                    while (left < right)
                                                                                                                    {
                                                                                                                        unsigned int middle = left + (right - left) / 2;
                                                                                                                        
                                                                                                                        if (x <  hashlist[middle])
                                                                                                                        {
                                                                                                                            right = middle;
                                                                                                                        }
                                                                                                                        else
                                                                                                                        {
                                                                                                                            left = middle + 1;
                                                                                                                        }			
                                                                                                                    }
                                                                                                        
                                                                                                                    if (x == hashlist[right])
                                                                                                                    {
                                                                                                                        // matched!
                                                                                                                    }
                                                                                                        

                                                                                                        • 0
                                                                                                          а, ну в общем, это как раз тот код, который попадает в 90% ошибочных! В таком виде. В программе я добавил fake-zero элемент, для решения проблемы с пустыми коллекциями и нахождением первого элемента (этот код его просто не находит).

                                                                                                          Вот и «поговорили» :)
                                                                                                      • +1
                                                                                                        Раз такое уже пошло, то и я свой код кину ))
                                                                                                        Поломайте мозги.
                                                                                                        Я для усложнения поставил себе задание — не использовать никакие ветвления и логические функции. На шарпе. Вот что получилось:

                                                                                                                static int BinarySearch(List<int> list, int num, Tuple<int, int> range)
                                                                                                                {
                                                                                                                    int midleIndex = (range.Item1 + range.Item2) / 2;
                                                                                                                    Func<int>[,] funcs = new Func<int>[,]
                                                                                                                                            {
                                                                                                                                                {
                                                                                                                                                    () => -1, () => -1, () => -1
                                                                                                                                                },
                                                                                                                                                {
                                                                                                                                                    () => BinarySearch(list, num, new Tuple<int, int>(range.Item1, midleIndex)),
                                                                                                                                                    () => midleIndex,
                                                                                                                                                    () => BinarySearch(list, num, new Tuple<int, int>(midleIndex + 1, range.Item2))
                                                                                                                                                }
                                                                                                                                            };
                                                                                                                    return funcs[(1 + Math.Sign(1 + 2 * (list.Count - range.Item2))) * Math.Sign(range.Item2 - range.Item1) / 2, Math.Sign(num - list[midleIndex]) + 1]();
                                                                                                                }
                                                                                                        
                                                                                                        


                                                                                                        Конечно, я не показываю пример, как надо писать на шарпе. Надеюсь, кому-то станет интересно почитать такой функционально-матричный подход.
                                                                                                        • 0
                                                                                                          Красивый вариант :)

                                                                                                          Но над чем тут ломать мозги? Все очевидно. Даже ошибку искать долго не пришлось: если при вычислении num — list[midleIndex] случится переполнение (например, num>2^30, list[midleIndex]<-2^30), то результат Sign будет неправильным.
                                                                                                          И говорить, что вызов функции из массива не является использованием ветвления, по-моему, не совсем честно…
                                                                                                          • 0
                                                                                                            Код я не серьезно писал )

                                                                                                            Понятно, что можно добавлять 0.5, все в дабл конвертнется, а знак брать тогда тоже можно. И код даже проще будет. Но как-то не хотелось даблами пользоваться. Прихоть такая.

                                                                                                            Внутри сайна есть ветвление и тоже это не очень чисто. А вот пользоваться массивом вместо ветвления и не называть его ветвлением — вполне честно. Понятно, что вызов такой его моделирует. Даже свич можно смоделировать. Но свич или иф — это структура кода, а здесь структура данных. Куда и функции примешались.

                                                                                                            Наверное можно еще что-то сделать такое, что упростит этот код. С ходу не придумал.
                                                                                                            • 0
                                                                                                              Понятно. Тут нужна двухуровневая схема — сначала отсеять пустые диапазоны, а уже потом сравнивать элемент с границами и с серединой. Код не упростится, но может стать надежнее.

                                                                                                              Про ветвление внутри Sign — тоже вызов. Сейчас подумаю :)
                                                                                                              • 0
                                                                                                                Да, можно.

                                                                                                                  mov ebx,eax
                                                                                                                  neg ebx
                                                                                                                  or ebx,eax
                                                                                                                  sar ebx,31
                                                                                                                  sar eax,31
                                                                                                                  add eax,eax
                                                                                                                  inc eax
                                                                                                                  and eax,ebx
                                                                                                                  ret
                                                                                                                
                                                                                                                • 0
                                                                                                                  Или даже так:

                                                                                                                  cdq
                                                                                                                  neg eax
                                                                                                                  sbb eax,eax
                                                                                                                  adc edx,edx
                                                                                                                  and eax,edx
                                                                                                                  ret
                                                                                                                  
                                                                                                                • 0
                                                                                                                  Как-то так:

                                                                                                                  int BinSearch(int[] arr,int val){
                                                                                                                    return BinSearch(arr,val,-1,arr.Length);
                                                                                                                  }
                                                                                                                  int BinSearch(int[] arr,int val,int left,int right){
                                                                                                                    return (new Func<int>[]{()=>~right,()=>BinSearchNE(arr,val,left,right)})[Math.Min(right-left-1,1)]();
                                                                                                                  }
                                                                                                                  int BinSearchNE(int[] arr,int val,int left,int right){
                                                                                                                    int mid=left+(right-left)/2;
                                                                                                                    return (new Func<int>[]{
                                                                                                                        ()=>BinSearch(arr,val,left,mid),
                                                                                                                        ()=>mid,
                                                                                                                        ()=>BinSearch(arr,val,mid,right))
                                                                                                                      }[Math.Sign((long)val-arr[mid])+1]();
                                                                                                                  }
                                                                                                                  


                                                                                                                  Не проверялось…
                                                                                                            • 0
                                                                                                              И, кстати, если искомый элемент больше последнего элемента списка — не получится ли midleIndex==list.Count? Выход индекса за границу может случиться…
                                                                                                              А зачем Math.Sign(1 + 2 * (list.Count — range.Item2))? Для защиты от некорректного входа? Ведь если в начале было 0<=range.Item1<=range.Item2<=list.Count, то оно так и останется. Или нет?
                                                                                                              • +1
                                                                                                                О, то бага! ))

                                                                                                                Вначале я до запятой, первый параметр массива написал так:
                                                                                                                Convert.ToInt32(range.Item2 <= list.Count && range.Item1 < range.Item2)

                                                                                                                Т.е. как раз условие, чтобы не вышли за пределы массива. И смоделировал потом сайнами. Но наверное конец рабочего дня, где-то ошибся. Точнее я смоделировал это условие так, как надо (надеюсь, не проверял только что), но то ли у меня четное (или нечетное) число элементов было, что проходил код. Решается эта бага замечательно. Вот в этой строчке надо так:

                                                                                                                int midleIndex = (range.Item1 + range.Item2 — 1) / 2;

                                                                                                                Если учитываем, что левая часть всегда не включается, то приводим рейджу с настоящими элементами.

                                                                                                                Но кажется, я перемудрил. Если сделать поправку со средним индексом, то достаточно сделать такое условие:
                                                                                                                Convert.ToInt32(range.Item1 < range.Item2)

                                                                                                                прошу прощения за ошибки, если даже сейчас ошибаюсь. Все таки после рабочего дня немного не так соображается. Финальная версия, надеюсь верная:

                                                                                                                static int BinarySearch(List<int> list, int num, Tuple<int, int> range)
                                                                                                                {
                                                                                                                    int midleIndex = (range.Item1 + range.Item2 - 1) / 2;
                                                                                                                    Func<int>[,] funcs = new Func<int>[,]
                                                                                                                        {
                                                                                                                            {
                                                                                                                                () => -1, () => -1, () => -1
                                                                                                                            },
                                                                                                                            {
                                                                                                                                () => BinarySearch(list, num, new Tuple<int, int>(range.Item1, midleIndex)),
                                                                                                                                () => midleIndex,
                                                                                                                                () => BinarySearch(list, num, new Tuple<int, int>(midleIndex + 1, range.Item2))
                                                                                                                            }
                                                                                                                        };
                                                                                                                    return funcs[Math.Sign(range.Item2 - range.Item1), Math.Sign(num - list[midleIndex]) + 1]();
                                                                                                                }
                                                                                                                


                                                                                                                как-то работает
                                                                                                                • 0
                                                                                                                  Остроумно :) выхода индекса за границу не произойдет, хотя может случиться обращение к элементу вне интервала. Но он есть всегда, а (-1)/2==0…
                                                                                                                  А Convert.ToInt32(range.Item1 < range.Item2) можно отнести к «логическим функциям» :( не прошло бы.
                                                                                                            • +1
                                                                                                              А мне понравился призыв автора написать свой поиск перед чтением топика. :)

                                                                                                              Вот что получилось в стиле STL для std::vector (собирать компилятором с поддержкой C++11):

                                                                                                              Поиск с возвратом любого попавшегося элемента: bs::find<тип, false>(где, что).
                                                                                                              Поиск с возвратом первого элемента из последовательности одинаковых: bs::find<тип, true>(где, что). Поиск первого элемента — тоже двоичный, а не последовательный.
                                                                                                              В обоих вариантах от типа E требуется только один оператор сравнения — меньше (<).

                                                                                                              #include <vector>
                                                                                                              #include <iterator>
                                                                                                              #include <iostream>
                                                                                                              
                                                                                                              namespace bs {
                                                                                                                  namespace impl {
                                                                                                                      template<typename E, bool find_first>
                                                                                                                      typename std::vector<E>::const_iterator find(const std::vector<E>& where, const E& what, const typename std::vector<E>::const_iterator& begin, const typename std::vector<E>::const_iterator& end)
                                                                                                                      {
                                                                                                                          typename std::vector<E>::const_iterator::difference_type size = std::distance(begin, end);
                                                                                                                          if (size == 0)
                                                                                                                              return where.end();
                                                                                                              
                                                                                                                          typename std::vector<E>::const_iterator center = begin + size / 2;
                                                                                                                          if (what < *center)
                                                                                                                              return find<E, find_first>(where, what, begin, center);
                                                                                                                          if (*center < what)
                                                                                                                              return find<E, find_first>(where, what, center+1, end);
                                                                                                                          if (find_first) {
                                                                                                                              typename std::vector<E>::const_iterator leftmost = find<E, find_first>(where, what, begin, center);
                                                                                                                              if (leftmost != where.end())
                                                                                                                                  return leftmost;
                                                                                                                          }
                                                                                                                          return center;
                                                                                                                      }
                                                                                                                  };
                                                                                                              
                                                                                                                  template<typename E, bool find_first>
                                                                                                                  typename std::vector<E>::const_iterator find(const std::vector<E>& where, const E& what)
                                                                                                                  {
                                                                                                                      return impl::find<E, find_first>(where, what, where.begin(), where.end());
                                                                                                                  }
                                                                                                              };
                                                                                                              
                                                                                                              int main(int argc, char* argv[])
                                                                                                              {
                                                                                                                  std::vector<int> input = { 10, 21, 34, 34, 34, 35, 41, 45, 49, 67, 102, 120, 120, 120, 120, 120, 120, 201 };
                                                                                                                  std::copy(input.begin(), input.end(), std::ostream_iterator<int>(std::cout, " "));
                                                                                                                  std::cout << std::endl << std::endl;
                                                                                                              
                                                                                                                  int what;
                                                                                                                  for(;;) {
                                                                                                                      std::cout << "Find what: ";
                                                                                                                      std::cin >> what;
                                                                                                              
                                                                                                                      typename std::vector<int>::const_iterator found = bs::find<int, true>(input, what);
                                                                                                                      if (found == input.end()) {
                                                                                                                          std::cout << "Not found" << std::endl;
                                                                                                                          continue;
                                                                                                                      }
                                                                                                              
                                                                                                                      std::cout << "Found at " << std::distance(static_cast<std::vector<int>::const_iterator>(input.begin()), found) << std::endl;
                                                                                                                  }
                                                                                                              
                                                                                                                  return 0;
                                                                                                              }
                                                                                                              
                                                                                                              • 0
                                                                                                                Вы неверно употребляете понятие «интервал». В контексте множеств чисел то, что вы называете интервалом, правильно называется отрезком.

                                                                                                                Разница между множествами: в множество чисел отрезка включаются ограничивающие его величины, а в множество интервала — как раз наоборот.

                                                                                                                Записываются соотверственно:
                                                                                                                • (left; right) — интервал;
                                                                                                                • [left; right] — отрезок.
                                                                                                                • 0
                                                                                                                  Скажите мне что вы курили, чтобы я этого никогда не пробовал.
                                                                                                                  • +1
                                                                                                                    Абсолютно ничего :-)
                                                                                                                    • 0
                                                                                                                      Тогда все правильно. Я этого никогда не делал.
                                                                                                                  • 0
                                                                                                                    Ну раз попросили написать перед прочтением, теперь хочется это «творчество» куда-то деть, беглым взглядом на правильные решения я понял, что мой вариант видимо немного избыточен, тем не менее пусть будет как есть. Заработало не с первого раза, но сложностей не было.

                                                                                                                    «спасибо» разработчикам хабра, видимо из-за недостатка дрочециферок теги source не работают

                                                                                                                    pastie.org/4128677
                                                                                                                    • 0
                                                                                                                      А где там режим поиска?
                                                                                                                    • +1
                                                                                                                      Зачем такой геморрой с порядком, в котором отсортирован массив? Вы пишете на C#? Используйте компаратор! Ну и выделять отдельный случай для mid = x совсем не обязательно. Просто сузим полуинтервал до размера 1 и проверим, равен ли его начальный элемент, искомому (Нередко, кстати, интересен наибольший, не превосходящий x). Заодно упростится поиск первого/последнего подходящего
                                                                                                                      • 0
                                                                                                                        Почему бы не рассматривать это как часть условия задачи — массив отсортирован в соответствии с компаратором, но заранее неизвестно, в прямом или обратном порядке. Если брать задачу в полном виде (3 режима поиска+2 возможных порядка) она становится достаточно интересной, чтобы заняться решением.
                                                                                                                        • +1
                                                                                                                          Ничуть! После проверки того, в правильном ли порядке отсортирован массив, компаратор можно просто поменять на противоположный.
                                                                                                                        • 0
                                                                                                                          Вообще да, от меня идея юзать компараторы почему-то сразу же ускользнула. А по поводу сужения полуинтервала до размера 1 — как именно вы будете сужать полуинтервал, если вам нужно первый/последний из дублирующих? Ведь когда мы сужаем, мы выбрасываем средний элемент
                                                                                                                          • 0
                                                                                                                            как раз таки средний выбрасывать не надо: если он не превосходит х — сделаем его левым концом
                                                                                                                            • 0
                                                                                                                              Окей, допустим у нас массив из двух элементов: {20, 30}. Какой следующий шаг? Ведь полуинтервал не сократится, он так и останется [0, 2)
                                                                                                                              • 0
                                                                                                                                (0+2)/2 = 1
                                                                                                                                т.е. дальше останется либо полуинтервал [0,1) либо [1,2)
                                                                                                                                • 0
                                                                                                                                  Смотрите, средний элемент — 1-й. Но поскольку мы его не выбрасываем, то у нас промежуток не меняется. Т.е. база рекурсии получается равна массиву из двух элементов, нет?
                                                                                                                                  • 0
                                                                                                                                    как раз таки средний выбрасывать не надо: если он не превосходит х — сделаем его левым концом

                                                                                                                                    Я понял — вы включаете средний элемент, только в одном случае, если сокращение интервала уходит в правую половину. Т.е. [0, 2) разбивается или на [0, 1) (средний не включен) или на [1, 2) (средний включен).

                                                                                                                                    Т.е. этот код будет искать последний элемент из дублирующих:
                                                                                                                                     if (array[middle] <= x)
                                                                                                                                        left = middle; // include middle
                                                                                                                                    else
                                                                                                                                        right = middle; // exclude middle
                                                                                                                                    

                                                                                                                                    А этот код будет искать первый элемент из дублирующих:
                                                                                                                                    if (array[middle] < x)
                                                                                                                                        left = middle + 1; // exclude middle
                                                                                                                                    else
                                                                                                                                        right = middle + 1; // include middle
                                                                                                                                    

                                                                                                                                    Но при этом эти коды мало того, что разные интервалы генерируют, в первом сравнение <=, а второе — просто <.
                                                                                                                                    • 0
                                                                                                                                      Будем считать во втором случае, что полуинтервал имеет вид (], тогда интервалы будут получаться одинаковыми
                                                                                                                          • 0
                                                                                                                            Такой вариант будет именно, что находить всегда последний.
                                                                                                                            Если надо первый, то меняем полуинтервал [) на (]
                                                                                                                            • 0
                                                                                                                              Как-то это неправильно, менять тип полуинтервала
                                                                                                                              • 0
                                                                                                                                ну это мысленно меняем. а по факту — это просто выбор начальных значений и того, куда можно присоединить среднее значение
                                                                                                                                • 0
                                                                                                                                  Почему неправильно? Это всего лишь условие проверки: определяем мы значение, равное заданному, как большее, чем надо, или как меньшее. У меня в коде, в сущности, так и делается:
                                                                                                                                  habrahabr.ru/post/146228/#comment_4922036

                                                                                                                                  В случае поиска первого элемента мы поддерживаем условие arr[left]<val<=arr[right] и в качестве ответа выдаем конечное значение right, если в нем находится val, а для поиска последнего — arr[left]<=val<arr[right], и ответом будет left. Если же значение не совпало с искомым, в обоих случаях выдается ~right.
                                                                                                                                  • 0
                                                                                                                                    Честно говоря, мне страшно читать ваш код (именование переменных)
                                                                                                                              • 0
                                                                                                                                Там всего 6 переменных. Переименуйте x1 в left, x2 — в right, а x3 — в middle. Думаете, станет понятнее? Понятного названия для переменной h, я, к сожалению, предложить не могу. В переводе на русский оно звучало бы примерно как «относительное расположение искомого элемента и элемента массива с индексов middle с учетом заданной операции сравнения, полученного порядка упорядоченния массива и возможного равенства этих двух элементов».
                                                                                                                                • 0
                                                                                                                                  Написал на Питоне за 20 минут. Случаи с числом элментов равным 0, 1 или 2 обрабатывал вручную.
                                                                                                                                  • 0
                                                                                                                                    Рискну предположить, что вы не читали статью Как же все-таки правильно написать двоичный поиск?
                                                                                                                                    • 0
                                                                                                                                      Прошуршал все комментарии и странно что никто не заметил(а возможно что-то я накрутил).
                                                                                                                                      Имеем в массиве 1 (200000) элемент с индексом 0.
                                                                                                                                      Пытаемся найти элемент со значение 300000(left 0 right 1) и предполагаемое место вставки получаем -2. Хотя должны получить 0.
                                                                                                                                      Это начиная со второй попытки.


                                                                                                                                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.