Exponential Search - better than Binary search? (Explained)

This video lecture explains exponential search algorithm with example and code as well. The complete code is posted in description section below so do check it out. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

[spetsnaz_]

In your given code, in the last line of the function exponentialSearch(), will it not be return binarySearch(arr, i/2, min(i, n-1), x); instead of return binarySearch(arr, i/2, min(i, n), x); ???

[AmandeepSingh-otst]

Bhai ekdum jhaakkass samjhaya hai❤️❤️..keep it up..lots of love from my side

[RANAND-xdzu]

Sir time and space complicity didn't understand fully please make one video on time and space which searching algorithm is best why and compare with another what difference could you explain in more detail

[saichennu]

Please.. please... Upload more videos on data structures based problems

[dollerbill]

Thank you vey much for your explanation and efforts for this video totally appreciate it. keep up the good work.

[ibrahimshaikh]

Very helpful, keep updating such new topic, thanks a lot

[ankitjhunjhunwala]

Great video sir! Just one observation, should n't expression (i<n && a[i]<=x) should be (i<n && a[j]<x), as if x is duplicated many times then i/2 may not be proper lower bound or we should keep track of lower bound instead of i/2 then it will work properly for duplicates.

[bm-ubzc]

Isn't the command "min(i, n-1)" unnecessary, because the while loop already has prevented, that n would be larger than i? (while i <n: i*2)

[DeepakGupta-zzvf]

Why are we incrementing i = i*2, why not x3 or x5 ???

[joshuakhoo]

What does min(i, n-1) do? Sorry im new to coding. As in why are there two parameters inside

[soniamalik]

Great Sir but one question plz do gets counted in one of worst complexities....and while finding runtime we take the max time...so we need to take 2^n instead of logN....

[sudershansingh]

But we're still using binary search right?
We've just reduced some computations but the algorithm runs in O(log n) still so why do all this can't we just do with pure binary search.

[SudeeptaSood]

hi, how is the exponential jump from i = 2, 4, 8... giving (logn) time complexity? can you let me know. thanks

[adityasingh]

Why we compared 0th element separately in beginning ?

[sperovita]

Can you provide the same code in MATLAB?

[rockdestrobreakz]

If 11 would be present in 5th, 6th or 7th index we can't find it.

[mohammedfahimullah]

why should be we give min(i, n-1).Instead of that can we give n-1 alone

[alexisandersen]

Hi, this is absolutely ridiculous.

Unless you have an extremely large array where modular exponentiation indexing becomes useful, ... You're far better off just doing a linear search, or maybe a binary search if the list is larger by an order of magnitude or two than a cache line.

Even If you had a million integers, linear search is still faster, however you might see improvement with a binary search at that scale.... Maybe.... It really depends if you are on hardware that can fetch polynomially ahead rather than linear ahead.

For this algorithm to net actually gains, you'd have to be searching through some obscenely massive collection of hashes indexing objects in a relatively remote record heap with two or more layers of pointer indirection... then it might be worth it. But you might actually be better off using modular exponentiation indexing.

The point is that anything outside of cache is obscenely slow by comparison, and a single short tight loop will optimize far better than a sequence of loops and a potentially recursive function call... and because of that being able to leverage the automatic cache prefetch using linear iteration is preposterously effective.

I mean.... We have multi gigahertz processor cores, you can linearly iterate through about a billion member list of candidates checking for equality in less than a second. Trust me, binary search isn't the problem.

In your algorithm, it could be argued that the overhead of the loops, and function calls alone will obliterate any gains you think you're getting from this algorithm at this scale and scales even several orders of magnitude greater. I don't care what your big O notation says.

[mjofficial.]

Exanple u took is completely ridiculous. Can't u take index and values different?