why binary search ?

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
SREEKANTH
New poster
Posts: 3
Joined: Sat Apr 28, 2012 1:12 am

why binary search ?

Post by SREEKANTH » Sat Apr 28, 2012 1:32 am

we have sequential search which is in o(n)

then y to go for binary search whose time=o(nlogn)+logn

o(nlogn) is for creating sorted array


if the soln u r saying is tht binary search is applied where already sorted input is available...

then can u giv examples of it?

or is there is any better anaylsis?

SREEKANTH
New poster
Posts: 3
Joined: Sat Apr 28, 2012 1:12 am

Re: why binary search ?

Post by SREEKANTH » Sat Apr 28, 2012 2:07 am

i think once using binary search... structure is geerated with in nlogn time.. but after that every search takes logn time on the corresponding pattern

SREEKANTH
New poster
Posts: 3
Joined: Sat Apr 28, 2012 1:12 am

Re: why binary search ?

Post by SREEKANTH » Sat Apr 28, 2012 2:08 am

can someone post better analysis?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: why binary search ?

Post by brianfry713 » Mon Apr 30, 2012 10:02 pm

What is your question? Yes O(log n) is faster than O(n). If there are a large number of queries=q and n is large then you might need a binary search.
Sequential search O(q*n)
Binary search O(n*log n)+O(q*log n)
Check input and AC output for thousands of problems on uDebug!

Branzila
New poster
Posts: 1
Joined: Fri Feb 13, 2015 8:29 am

Re: why binary search ?

Post by Branzila » Fri Feb 13, 2015 8:32 am

Can anyone describe/elaborate the maximum subarray 2D algorithm with example?
You can join us for best 642-902 pass4sure dumps exam pass4sure 220-802 training solutions. Our usna contains all those materials you want to pass for real Rasmussen College

Post Reply

Return to “Algorithms”