Binary search algorithm

An example of the implementation of a binary search algorithm in the Julia programming language, designed to search for a given element in a sorted array.

Introduction

Binary search is an efficient algorithm for searching for an element in a sorted array. The basic idea is to divide the array in half at each step and compare the desired element with the element in the middle. This allows you to significantly reduce the number of operations compared to linear search. The algorithm has a time complexity which makes it very fast for large amounts of data.

The algorithm solves the problem of searching for a specific value in an ordered data set. It is widely used in computer science, databases, sorting algorithms, and other fields where a quick element search is required.

The main part

Definition of function and parameters

Function binarysearch accepts a sorted vector lst and the desired value val. The function is parameterized by the type T, which allows you to work with any type of data

function binarysearch(lst::Vector{T}, val::T) where T
    # Инициализируем нижнюю границу поиска
    low = 1
    # Инициализируем верхнюю границу поиска (длина массива)
    high = length(lst)
    
    ## Основной цикл поиска
    
    # Продолжаем поиск пока нижняя граница не превысит верхнюю
    while low ≤ high
        # Находим середину текущего диапазона
        # Оператор ÷ выполняет целочисленное деление
        mid = (low + high) ÷ 2
        
        # Сравниваем элемент в середине с искомым значением
        if lst[mid] > val
            # Если элемент в середине больше искомого,
            # сдвигаем верхнюю границу на позицию перед серединой
            high = mid - 1
        elseif lst[mid] < val
            # Если элемент в середине меньше искомого,
            # сдвигаем нижнюю границу на позицию после середины
            low = mid + 1
        else
            # Если элемент в середине равен искомому,
            # возвращаем индекс найденного элемента
            return mid
        end
    end

    ## Обработка случая, когда элемент не найден

    # Если мы вышли из цикла, значит элемент не найден
    # Возвращаем 0 как признак отсутствия элемента
    # (в Julia индексация начинается с 1, поэтому 0 не является допустимым индексом)
    return 0
end

binarysearch

An example of using the function

Creating a sorted array for testing

test_array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];

# Ищем существующий элемент
result1 = binarysearch(test_array, 7)
println("Поиск элемента 7: индекс = $result1")  # Должно вернуть 4

# Ищем несуществующий элемент
result2 = binarysearch(test_array, 6)
println("Поиск элемента 6: индекс = $result2")  # Должно вернуть 0

# Ищем первый элемент
result3 = binarysearch(test_array, 1)
println("Поиск элемента 1: индекс = $result3")  # Должно вернуть 1

# Ищем последний элемент
result4 = binarysearch(test_array, 19)
println("Поиск элемента 19: индекс = $result4")  # Должно вернуть 10

Поиск элемента 7: индекс = 4
Поиск элемента 6: индекс = 0
Поиск элемента 1: индекс = 1
Поиск элемента 19: индекс = 10

Conclusion

In this example, we looked at the implementation of the Julia binary search algorithm. We have managed to create an efficient function that can quickly find elements in sorted arrays. The algorithm uses the principle of "divide and conquer", which allows to achieve logarithmic time complexity. . This is especially important when working with large amounts of data, where linear search would be ineffective. The implementation supports generics, which makes it flexible for working with different data types, provided that they support comparison operations.

The example was developed using materials from Rosetta Code