Блог пользователя Baiterr

Автор Baiterr, история, 19 месяцев назад, По-английски

help pls

  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

»
19 месяцев назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

Ternary search helps in such scenarios where the function is first increasing and then decreasing or first decreasing and then increasing

»
19 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

at linear functions the array is increase or decrease we use binary search but at quadratic function it decrease then increase or increase then decrease we use tirnary search u could see the visualization of a function at geogebra for example

»
19 месяцев назад, скрыть # |
 
Проголосовать: нравится -7 Проголосовать: не нравится

You don't binary search. Instead, you use ternary search

»
19 месяцев назад, скрыть # |
 
Проголосовать: нравится +36 Проголосовать: не нравится

you can do binary search not on the initial array (for example $$$arr$$$), but on $$$arr_i - arr_{i+1}$$$. Firstly sign of this function will be negative, then positive, so you can use binary search

»
19 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

use binary search and Sparse Table