Реализации алгоритмов/Двоичный поиск: различия между версиями
Содержимое удалено Содержимое добавлено
Заменён пример на Python; добавлен пример на C# |
Примеры для C# и Python оптимизированы; добавлены рекурсивные варианты |
||
Строка 124:
</source>
==[[w:C_Sharp|C# 7.0+]]==
Цикл:
<source lang="csharp">
static (bool, int) BinarySearch <T> (T[]
{
int left = 0;
for (int right =
{
if (sorted_values[left].CompareTo(value) == 0)
return (true, left)
middle = left + (right - left) / 2;
var c =
if (c == 0)
if (middle == left + 1)
return (true, middle);
right = middle + 1;
}
if ((c < 0) == descending)
right = middle;
Строка 140 ⟶ 149 :
left = middle + 1;
}
return
}
</source>
Рекурсия:
<source lang="csharp">
public static (bool, int) BinarySearch <T> (T[] sorted_values, int value, bool descending = false) where T : IComparable
{
// Внутренняя рекурсивная функция
(bool, int) SearchOnRange (int left, int right)
{
if (left >= right)
return (False, left);
if (sorted_values[left] == value)
return (True, left);
int middle = left + (right - left) / 2;
return middle == left + 1
? (True, middle)
: SearchOnRange(left, middle + 1);
return (sorted_values[middle] < value) == descending
? SearchOnRange(left, middle)
: SearchOnRange(middle + 1, right);
}
// Тело внешней нерекурсивной функции
return SearchOnRange(0, sorted_values.Length());
}
</source>
Строка 253 ⟶ 288 :
==[[w:Python|Python]]==
'''Принимаются:'''
* список значений, упорядоченных по возрастанию либо убыванию;
* искомое значение; его тип должен соответствовать типам элементов списка;
* необязательный параметр логического типа, указывающий, считается ли список отсортированным по возрастанию (False, используется по умолчанию) или по убыванию (True).
'''Возвращается:''' кортеж (tuple) из двух значений:
* логическое значение: True (если искомое значение присутствует в списке), либо False (если отсутствует).
* индекс найденного в списке значения, либо индекс, по которому можно вставить в список отсутствующее значение не нарушая упорядоченности его элементов.
Цикл:
<source lang="python">
def binary_search (
left = 0
right = len(
while left < right:
if sorted_values[left] == value:
return (True, left)
middle = left + (right - left) // 2
if
return (True, middle)
▲ if (sorted_list[middle] < value) == descending:
right = middle + 1
if (sorted_values[middle] < value) == descending:
right = middle
else:
left = middle + 1
return
</source>
Рекурсия:
<source lang="python">
def binary_search (sorted_values, value, descending=False):
def search_on_range (left, right):
if left >= right:
return (False, left)
if sorted_values[left] == value:
return (True, left)
middle = left + (right - left) // 2
if sorted_values[middle] == value:
if middle == left + 1:
return (True, middle)
else:
return search_on_range(left, middle + 1)
if (sorted_values[middle] < value) == descending:
return search_on_range(left, middle)
else:
return search_on_range(middle + 1, right)
return search_on_range(0, len(sorted_values))
</source>
{{BookCat}}
| |||