FenWick's blog

Need Help in C++
By FenWick, history, 4 years ago, In English

Can we do Threading in Binary Search?

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Probably not since binary search is inherently sequential, and threading isn't useful in competitive programming anyway since online judges that I know of run on a single core and/or count the sum of the times taken by all threads.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why not? In normal binary search, we divide our interval into 2 subintervals, run 1 check function and achieve time complexity O(log_2(n)). With threading, we can divide it into 3 subintervals and run 2 check functions in parallel so time complexity is O(log_3(n)), etc.

→ Reply