Реализации алгоритмов/Двоичный поиск: различия между версиями

Примеры для C# и Python оптимизированы; добавлены рекурсивные варианты
(Заменён пример на Python; добавлен пример на C#)
(Примеры для C# и Python оптимизированы; добавлены рекурсивные варианты)
</source>
 
==[[w:C_Sharp|C# 7.0+]]==
 
Цикл:
 
<source lang="csharp">
static (bool, int) BinarySearch <T> (T[] arraysorted_values, int value, bool descending = false) where T : IComparable
{
int left = 0;
for (int right = arraysorted_values.Length, middle; left < right; )
{
if (sorted_values[left].CompareTo(value) == 0)
return (true, left)
middle = left + (right - left) / 2;
var c = arraysorted_values[middle].CompareTo(value);
if (c == 0)
return middle;{
if (middle == left + 1)
return (true, middle);
right = middle + 1;
}
if ((c < 0) == descending)
right = middle;
left = middle + 1;
}
return ~(false, left);
}
</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;
if (sorted_listsorted_values[middle] <== value) == descending:
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>
 
==[[w:Python|Python]]==
'''Принимаются:'''
* список значений, упорядоченных по возрастанию либо убыванию;
* искомое значение; его тип должен соответствовать типам элементов списка;
* необязательный параметр логического типа, указывающий, считается ли список отсортированным по возрастанию (False, используется по умолчанию) или по убыванию (True).
'''Возвращается:''' кортеж (tuple) из двух значений:
* логическое значение: True (если искомое значение присутствует в списке), либо False (если отсутствует).
* индекс найденного в списке значения, либо индекс, по которому можно вставить в список отсутствующее значение не нарушая упорядоченности его элементов.
 
Цикл:
 
<source lang="python">
def binary_search (sorted_listsorted_values, value, descending=False):
left = 0
right = len(sorted_listsorted_values)
while left < right:
if sorted_values[left] == value:
return (True, left)
middle = left + (right - left) // 2
if sorted_listsorted_values[middle] == value:
returnif middle == left + 1:
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 ~(False, left)
</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}}
74

правки