Java: бинарный поиск

Цель: научится писать красивый и эффективный код.

Задача: перед использованием какого-либо алгоритма, реализация которого есть в библиотеках, написать самому его реализацию.

Решение:

недавно на хабре был замечательный пост про то, что в действительности даже простые алгоритмы типа дихотомии (бинарный поиск) могут написать только 10% программистов. В действительности этот пост оказался проверкой своих качеств как программиста для тех, кто его читал. И правда, многие в комментариях честно признавались, что написание этого алгоритма заняло у них от 30 до 90 минут. Решил и я попробовать, и спустя 40 минут нарисовалось следующее:

	public static int binarySearch(int numb, int[] array) {
		int border = (int) Math.floor(array.length/2);
		int current = border;
		int tmp = array[current];
		do {
			if (tmp == numb) {
				return current;
			}
			if (numb == array[current - border]) {
				return current-border;
			}
			
			if (numb == array[current + border - 1]) { // Тут внесена правка, см. комментарии
				return current+border;
			}

			border = (int) Math.floor(border/2);
			if (tmp < numb) {
				tmp = array[current + border];
				current += border;
			} else {
		        tmp = array[current - border];
		        current -= border;
			}
		} while (border != 0);
		return -1;
	}

Что, конечно, было довольно громоздко и не слишком быстро (и довольно грязно), но работало. Однако самое интересное произошло, когда я нашел исходные коды реализации этого алгоритма в стандартной библиотеке java.util.arrays:

    // Like public version, but without range checks.
    private static int binarySearch0(int[] a, int fromIndex, int toIndex,
				     int key) {
	int low = fromIndex;
	int high = toIndex - 1;

	while (low <= high) {
	    int mid = (low + high) >>> 1;
	    int midVal = a[mid];

	    if (midVal < key)
		low = mid + 1;
	    else if (midVal > key)
		high = mid - 1;
	    else
		return mid; // key found
	}
	return -(low + 1);  // key not found.
    }

Исходники находятся в архиве src.zip, который лежит в JDK (у меня это было в C:\Program Files\Java\jdk1.6.0_18).
Самое интересно (и после ставшее очевидным), что целочисленное деление на два можно выполнять простым поразрядным беззнаковым оператором сдвига вправо a >>> n, который смещает биты в числе a вправо на n разрядов. Более того, как совершенно верно заметил один пользователь в ЖЖ:

В оригинальной реализации даже не нужна проверка на переполнение, потому что, даже если происходит переполнение, потом мы сдвигаем сумму вправо на 1 бит, последний бит заполняя ноликом (потому что >>>) — а не просто деля получившуюся (возможно, отрицательную в результате переполнения) сумму пополам, таким образом, даже если числа были по размеру как близкие к максимуму int’ы, всё равно число посередине будет найдено корректно.

Вот такая вот история с простой моралью: чтобы расти дальше, необходимо учится у лучших и на своих ошибках.

Ссылки в записи

  • Запись на habrahabr.ru о том, что по исследованиям Дональда Кнута, только 10% программистов могут написать реализацию двоичного поиска