Простая Задачка с массивом

@Lex Backer · Регистрация: 28.01.2016

Author24 — интернет-сервис помощи студентам

Решил данную задачку, но в ответе написали, что я не использую тот факт, что массив отсортирован, и получается не оптимально.

Помогите разобраться с примером.
Есть отсортированный по возрастанию массив из 1000 элементов. Есть число, которое точно есть в этом массиве. Выведите на экран его порядковый номер.

Не используйте готовый функций поиска, напишите код.
Ваш код должен использовать то, что массив уже отсортирован, и быть по возможности оптимальным.

@Para bellum · 22.05.2018, 10:10

Код, написанный Вами, покажите.

@tarasalk · 22.05.2018, 10:27

Подозреваю что там перебор всех элементов. Попробуйте реализовать бинарный поиск.

@Lex Backer · 22.05.2018, 11:35 **[ТС]**

PHP

foreach($array as $key=>$item)
    if($item === $needle){
        print $key; break;
    }

@Para bellum · 22.05.2018, 13:17

Бинарный поиск:

PHP

function array_find(array $haystack, $needle)
{
    if (!$haystack) {
        return;
    }
    
    $offset = 0;
    $end    = count($haystack) - 1;
    
    while ($offset < $end) {
        $middle = $offset + (($end - $offset) >> 1);
        
        if ($haystack[$middle] >= $needle) {
            $end = $middle;
        } else {
            $offset = $middle + 1;
        }
    }
    
    if ($haystack[$end] === $needle) {
        return $end;
    }
}

Добавлено через 1 минуту
На малом кол-ве элементов в массиве работает медленнее, чем простой перебор. На большом кол-ве в десятки раз быстрее.

@Lex Backer 0 / 0 / 0 Регистрация: 28.01.2016 Сообщений: 4
		1
	Простая Задачка с массивом 22.05.2018, 10:00. Показов 1642. Ответов 4 Метки нет (Все метки) Решил данную задачку, но в ответе написали, что я не использую тот факт, что массив отсортирован, и получается не оптимально. Помогите разобраться с примером. Есть отсортированный по возрастанию массив из 1000 элементов. Есть число, которое точно есть в этом массиве. Выведите на экран его порядковый номер. Не используйте готовый функций поиска, напишите код. Ваш код должен использовать то, что массив уже отсортирован, и быть по возможности оптимальным. 0

@Para bellum 5753 / 4133 / 1507 Регистрация: 06.01.2011 Сообщений: 11,276
	22.05.2018, 10:10	2
	Код, написанный Вами, покажите. 0

@tarasalk 1992 / 1216 / 440 Регистрация: 13.06.2013 Сообщений: 4,115
	22.05.2018, 10:27	3
	Подозреваю что там перебор всех элементов. Попробуйте реализовать бинарный поиск. 2

	22.05.2018, 13:17

Опции темы

Простая Задачка с массивом

Решение