21–30 of 149 posts
Does the algorithm described for finding a number in an unsorted array using minimal checks really work? Probably is addressed more in the book but didn't see my concerns in the post. The algorithm I am referring to is: " 1. Check if the current item is the desired one. If it is, return success if the pointer is within the array bound and return failure if it isn’t; otherwise 2. Increment the pointer and continue. "…
> the first section after the chapter intro deals with the basic problem of searching for an item in an unsorted array. The simplest algorithm should be familiar to all programmers. Start your pointer at the head of the array, then do the following in a loop: > Check if the current item is the desired one. If it is, return success; otherwise > Check if the pointer is past the array bound. If it is, return failure; ot…
I do this with tipping. If the price is 22.95 I tip -22.95 and the total charge is only $0.00 ... save a ton of money!
Edit: My version is "an authorized adaption, global edition" overseen by two Malaysian professors and printed in Malaysia by Pearson Global. I'm not sure what adaption means in the printing industry.
Edit2: One of the author's acknowledges the terrible amount of errors on their personal page https://www.amazon.com/gp/customer-reviews/RK8QVG9TMSUIF/ref... which I just discovered and did not know at the time I read the book (I bought this so I could understand MIXAL in TAOCP, Vol 1).
Does the algorithm described for finding a number in an unsorted array using minimal checks really work? Probably is addressed more in the book but didn't see my concerns in the post. The algorithm I am referring to is: " 1. Check if the current item is the desired one. If it is, return success if the pointer is within the array bound and return failure if it isn’t; otherwise 2. Increment the pointer and continue. "…
> I think it assumes that all values will be found in memory somewhere
That assumption is not made; the post does cover this. You left out the beginning of the algorithm:
> A more clever search algorithm can do it with just one bound check in all cases. Tack the desired item on to the end of the array, then start your pointer at the head of the array and do the following in a loop:
It's not clear to me how you're supposed to "tack the item on to the end of the array", though. That's not an operation arrays naturally support. If you recopy the array so you can add your sentinel value, then you're replacing an average n/2 bounds checks with a guaranteed n copies.
Does the algorithm described for finding a number in an unsorted array using minimal checks really work? Probably is addressed more in the book but didn't see my concerns in the post. The algorithm I am referring to is: " 1. Check if the current item is the desired one. If it is, return success if the pointer is within the array bound and return failure if it isn’t; otherwise 2. Increment the pointer and continue. "…
> A more clever search algorithm can do it with just one bound check in all cases. Tack the desired item on to the end of the array, then start your pointer at the head of the array and do the following in a loop: ...
So you will do exactly one more value check in the case where the element is not in the list, and n - 1 less bounds checks.
Does the algorithm described for finding a number in an unsorted array using minimal checks really work? Probably is addressed more in the book but didn't see my concerns in the post. The algorithm I am referring to is: " 1. Check if the current item is the desired one. If it is, return success if the pointer is within the array bound and return failure if it isn’t; otherwise 2. Increment the pointer and continue. "…
> Does the algorithm described for finding a number in an unsorted array using minimal checks really work? Probably is addressed more in the book but didn't see my concerns in the post. > I think it assumes that all values will be found in memory somewhere That assumption is not made; the post does cover this. You left out the beginning of the algorithm: > A more clever search algorithm can do it with just one bound…
>It's not clear to me how you're supposed to "tack the item on to the end of the array", though
The algorithm mentions pointers so I think it means temporarily change a value in memory that is after the array with the array value. I'd be worried about how this would work if there are multiple threads, though, in case another thread wants to access the memory that was temporarily swapped out. (Edit: as other poster mentions, would be helpful to have an extra entry in the array for this purpose.)
If the 'array' is internally something like a vector, then you can add it on to the end quickly by appending a node to the tail of a linked list.
> the first section after the chapter intro deals with the basic problem of searching for an item in an unsorted array. The simplest algorithm should be familiar to all programmers. Start your pointer at the head of the array, then do the following in a loop: > Check if the current item is the desired one. If it is, return success; otherwise > Check if the pointer is past the array bound. If it is, return failure; ot…
Does the algorithm described for finding a number in an unsorted array using minimal checks really work? Probably is addressed more in the book but didn't see my concerns in the post. The algorithm I am referring to is: " 1. Check if the current item is the desired one. If it is, return success if the pointer is within the array bound and return failure if it isn’t; otherwise 2. Increment the pointer and continue. "…