Поиск с барьером

Разновидностью линейного поиска является поиск с барьером, который заключается в том, что в конец исследуемого массива добавляется искомый элемент.Выигрыша в сложности алгоритма этот метод не дает, она также составляет O(N). Он позволяет избавиться от условия проверки достижения искомого элемента в цикле.

Однако недостаток метода заключается в необходимости увеличивать пазмер массива на один элемент. Это можно сделать в большинстве случаев только путем создания нового массива увеличенной на единицу размерности и копирования элементов из старого с последующим добавлением искомого элемента.
Далее приводится реализация алгоритма на разных языках программирования.

#include <stdio.h>
#include <stdlib.h>

int barrier_search(const int ar[], int length, int item)
{
	int i = 0;
	int* resized_arr = malloc(sizeof(int) * (length + 1));

	for (int j = 0; j < length; j++)
		resized_arr[j] = ar[j];

	resized_arr[length] = item;

	int new_length = length+1;
	
	while (resized_arr[i] != item)
		i++;

	free(resized_arr);

	if (i < new_length-1) 
		return i;

	return -1;
}

int main(void)
{
	const int arr[] = {1,2,3,4,5};

	int item = 1;
	int length = sizeof(arr) / sizeof(*arr);
	int found = barrier_search(arr, length, item);

	printf("item = %d, index = %d\n", item, found);

	return 0;
}

internal class Program
{
    static int BarrierSearch(T[] arr, T item) where T : IComparable
    {
        int length = arr.Length;
        Array.Resize(ref arr, ++length);
        arr[length - 1] = item;

        int i = 0;

        while (arr[i].CompareTo(item) != 0)
        {
            i++;
        }

        if (i < length - 1)
        {
            return i;
        }

        return -1;
    }

    static void Main(string[] args)
    {
        int[] arr = { 5, 12, 3, 8, 4, 7 };
        int item = 8;
        int index = BarrierSearch(arr, item);

        Console.WriteLine($"Array: {string.Join(" ", arr1)}\nitem = {item}, index = {index}");

        Console.ReadKey();
    }
}

<?php
function BarrierSearch(array $arr, int $item) : int 
{
    $arr[count($arr)]=$item;
    $i=0;
    $length=count($arr);

    while($arr[$i]!=$item) {
        $i++;
    }

    if ($i<$length-1) {
        return $i;
    }

    return -1;
}

function BarrierSearch(arr, item) {
    if (Array.isArray(arr)) {

        arr[arr.length]=item;
        let i=0;
        const len=arr.length;
        
        while(arr[i]!==item) {
             i++;
        }
 
        if (i<len-1) {
           return i;
        }
 
        return -1;
     }
     else {
         throw new Error("First argument must be of type Array");
     }
}