Unity: Всё, что вы не знали о разработке

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

Допустим, что у нас есть отсортированный массив чисел:
1 2 6 8 56 234 745 998 1010

Как нам определить, что в этом массиве есть какое-то число?
Самый простой вариант - пройти линейно от первого элемента до последнего. Таким образом мы получаем O(n) (Если кто не видел пост https://www.tgoop.com/unsafecsharp/97).

Но как это сделать быстрее?
На этом месте те, кто не знает, может остановиться и подумать

На самом деле существует небольшой лайфхак: если вы видите что-нибудь отсортированное (массив это или матрица - не важно) и задача - поиск, то сложность всегда будет log(n). В теории можно придумать алгоритм, который будет еще умнее, но сложность от этого не изменится.

Итак, для начала нам нужно взять центральный индекс, то есть length / 2. После чего у нас массив разделится на два подмассива, при этом слева элементы будут всегда меньше искомого, а справа - больше.
Т.е. если центральный элемент не тот, который мы ищем, то мы сразу отсеиваем половину элементов массива и берем индекс снова центральный от подмассива.
Ищем 2:
[1 2 6 8 56 234 745 998 1010]
[1 2 6 8 56]
[1 2 6]

Т.е. мы за 3 итерации нашли число. Вот это отбрасывание половины и есть log(n).

#search #binary #code #algorithms

Telegram

Unity: Всё, что вы не знали о разработке

Немного про оценку сложности алгоритмов.

Вы, наверное, не раз сталкивались с таким понятием как сложность алгоритмов. Существует несколько нотаций, которыми можно описать сложность алгоритма, в основном используется О-нотация (или О-большое), т.к. она описывает…

🥱16👍12🔥5

www.tgoop.com/unsafecsharp/113

1.04K viewsJun 17, 2023 at 08:10

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

Допустим, что у нас есть отсортированный массив чисел:
1 2 6 8 56 234 745 998 1010

Как нам определить, что в этом массиве есть какое-то число?
Самый простой вариант - пройти линейно от первого элемента до последнего. Таким образом мы получаем O(n) (Если кто не видел пост https://www.tgoop.com/unsafecsharp/97).

Но как это сделать быстрее?
На этом месте те, кто не знает, может остановиться и подумать

На самом деле существует небольшой лайфхак: если вы видите что-нибудь отсортированное (массив это или матрица - не важно) и задача - поиск, то сложность всегда будет log(n). В теории можно придумать алгоритм, который будет еще умнее, но сложность от этого не изменится.

Итак, для начала нам нужно взять центральный индекс, то есть length / 2. После чего у нас массив разделится на два подмассива, при этом слева элементы будут всегда меньше искомого, а справа - больше.
Т.е. если центральный элемент не тот, который мы ищем, то мы сразу отсеиваем половину элементов массива и берем индекс снова центральный от подмассива.
Ищем 2:
[1 2 6 8 56 234 745 998 1010]
[1 2 6 8 56]
[1 2 6]

Т.е. мы за 3 итерации нашли число. Вот это отбрасывание половины и есть log(n).

#search #binary #code #algorithms

BY Unity: Всё, что вы не знали о разработке