Szathmáry László honlapja @ DEIK | DLang / Binary search

(1) binary search

import bisect

# see also https://realpython.com/binary-search-python/
def binary_search(elements, value) -> int:
idx = bisect.bisect_left(elements, value)
if idx < len(elements) and elements[idx] == value:
return idx
# else
return -1 # not found

def main():
numbers = [1, 3, 4, 7, 9] # sorted

print(binary_search(numbers, 7)) # 3 (index position)

print(binary_search(numbers, 5)) # -1 (not found)

import std.stdio;

import std.range; // assumeSorted()
import std.algorithm;

void main()
{
int[] numbers = [1, 3, 4, 7, 9]; // sorted
// let D know that it's sorted:
auto r = assumeSorted(numbers); // returns a SortedRange

writeln(r.contains(7)); // true
writeln(r.contains(5)); // false

writeln("---");

int[] values = [8, 5, 1, 3]; // NOT sorted
auto r2 = values.sort(); // sort() returns a SortedRange

writeln(r2.contains(5)); // true
writeln(r2.contains(9)); // false
}

Notes:

In Python, bisect_left() returns the would-be position of a non-existing element. For instance, if you're looking for 5 in [1, 4, 7], it returns the position between 4 and 7. That's why we need the extra if statement after calling bisect_left().
In D, sort() sorts the list in-place AND returns a SortedRange.