So I was reading about Recursive searching in a binary search algorithm and I saw a line that says, that with every computation where you don't find the result, you cut the array you are looking through in half and create a new array. Is it really necessary to make a new array with every computation instead of adjusting the start and end index of the array you started with?
4
-
2Where were you reading that?Normally for binary search, there is no need to create a new array.Renjith– Renjith2013-01-23 13:22:06 +00:00Commented Jan 23, 2013 at 13:22
-
1there's not only no need, you really shouldn't do it, otherwise your space consumption will go from O(n) to ~O(n^2) (not a tight bound but you'd be heading towards there)tttthomasssss– tttthomasssss2013-01-23 13:23:56 +00:00Commented Jan 23, 2013 at 13:23
-
you can delete the old array, so you will save space after the copy.Simulant– Simulant2013-01-23 13:24:55 +00:00Commented Jan 23, 2013 at 13:24
-
Thanks for the comments so far. I was pretty curious about this. But why do I get downvotes exactly? My question is pretty legit.OmniOwl– OmniOwl2013-01-23 13:25:30 +00:00Commented Jan 23, 2013 at 13:25
Add a comment
|
2 Answers
sure you can just adjust the start and end index. This is the implementation. What you are reading is an easy description of the algorithm, the implementation can differ if it still does the work.
Comments
As @tttthomasssss noted in his comment, you should avoid copying the array (even part of it) while searching through it.
Not only will this increase your space consumption dramatically from O(1) to O(n), because you need extra memory to keep a partial copy of an original array, but the computational complexity of such an implementation will also be suboptimal (see https://cs.stackexchange.com/q/87728/185168) since you traverse the elements of the original array sequentially to make a copy.
