Baiterr's blog

how to binary seach an array that first increasing then decreasing
By Baiterr, history, 32 hours ago, In English

help pls

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
32 hours ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
32 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
31 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Errichto's video about binary search is very helpful.

→ Reply
»
28 hours ago, # |
  Vote: I like it -7 Vote: I do not like it

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

→ Reply
»
20 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

thank you all

→ Reply
»
18 hours ago, # |
  Vote: I like it +36 Vote: I do not like it

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

→ Reply
»
18 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

use binary search and Sparse Table

→ Reply
  • »
    »
    14 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ah yes, a newbie doing binary search on Sparse Table, classic.

    I doubt a normal newbie has heard of Sparse Table.

    → Reply
»
16 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Check this out https://cp-algorithms.com/num_methods/ternary_search.html

→ Reply
»
14 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

https://oi-wiki.org/basic/binary/#%E4%B8%89%E5%88%86%E6%B3%95 This may help you.

→ Reply