Timeline for Binary Search in C - Optimization
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 12, 2013 at 14:55 | comment | added | Aseem Bansal | After some thinking I think I might have found the best of both worlds. I'll update with a code that uses the same number of comparisons as you have suggested while still taking care of accessing uninitialized memory. | |
| Jul 10, 2013 at 9:13 | comment | added | Aseem Bansal |
Your code is missing a brace after the last else and shouldn't it be 2 * lg(N) + 2. In the final case there are 2 comparisons, 1 for the if and 1 inside it.
|
|
| Jul 10, 2013 at 9:06 | comment | added | Aseem Bansal |
About declaring mid and element as const, should any variable, that isn't changed in the called function, be decalred const? I understand that declaring arr as const is relevant because it is a pointer that can be changed but the calling function's original value passed to the variable element cannot be effected here. Is this declaration of const for the purposes of clarity and perhaps a security measure in the scope of the called function?
|
|
| Jul 10, 2013 at 8:53 | comment | added | Aseem Bansal |
Any function that needs to called in other files by including the header files shouldn't be static. But these functions can access the static functions from the files from which they are called. Am I correct? As an example of what I think you have said, in this question the merge_parts function should be static but the merge_sort shouldn't be. Declaring merge_parts as static won't effect the use of merge_sort in another file. Correct me if I am wrong.
|
|
| Jul 9, 2013 at 19:54 | comment | added | ruds |
My solution has the downside that it accesses uninitialized memory when max < 0 initially, which may happen e.g. when code doesn't check for an empty array before calling bin_search
|
|
| Jul 9, 2013 at 19:53 | history | answered | ruds | CC BY-SA 3.0 |