Searching

Даден е списък с разбъркани фак. номера. Трябва да напишем функция, която ще приложим точно веднъж и никога повече, за да намерим факултетния номер “140”. Кое ще е най-бързото и подходящо търсене в тази ситуация?

• Linear search

• Binary search

• Ternary search

• Jump search

Даден е списък с точки. Трябва да напишем функция, която ще приложим многократно за намираме на максималния брой точки. Кое ще е най-бързото и подходящо търсене в тази ситуация?

• Linear

• Sort+Binary search

• Jump search

• Зависи от големината на входния масив

Ако приложим lower_bound(v.begin(), v.end(), 30) за следния масив с числа:

10, 20, 30, 30, 30, 40, 50.

Какво очаваме като индекс

• 1

• 2

• 4

• 5

Ако приложим upper_bound(v.begin(), v.end(), 30) за следния масив с числа:

10, 20, 30, 30, 30, 40, 50.

Какво очаваме като индекс

• 1

• 2

• 4

• 5

Binary search винаги е по-добър от Linear search

• ДА

• НЕ

• Само на черния петък

Каква е сложността на jump search, ако самия jump=1(Скачаме през всяко число)

• Sqrt(N)

• Log(N)

• N

• Друга