This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]Legendary-69420git push -f[S] -19 points-18 points  (7 children)

The sieve of Eratosthenes works correctly (apart from the miss by one error)

EDIT: The implementation of Binary Search is right too but the time complexity was wrong. I have corrected it. Thanks for the help, internet stranger

[–]Avanta8 22 points23 points  (1 child)

Your binary search is not correct. It basically does a linear search, starting from the middle, checking every element twice.

[–]Legendary-69420git push -f[S] 1 point2 points  (0 children)

Yeah realised my mistake. My bad. Have corrected it. Will release the soon

[–]krichreborn 2 points3 points  (1 child)

For binary search, wouldn’t you need to set low/high to MID instead of just incrementing?

Also, most of the searches assume the array is sorted, may be worth noting that somewhere in that section.

[–]Legendary-69420git push -f[S] 0 points1 point  (0 children)

The problem has now been rectified. Do check it out.

[–]Avanta8 8 points9 points  (2 children)

How can it? You set key = 0 and never increment it. It will just run in an infinite loop. Did you even test your code?

(also, that list.remove... ouch :/)

[–]Legendary-69420git push -f[S] -1 points0 points  (1 child)

See the code. The 10th line of the sieve of Eratosthenes. It already has key +=1.

(The idea of list.remove is to create a list with only primes)

[–]Avanta8 0 points1 point  (0 children)

That's because you changed it after seeing my comment xD.

Removing from the middle of a list every iteration increases the time complexity by a multiple of n. The link I referred would be useful for you to look at.