That's not really elogant...
By k, I assume you are talking about k=alen(arr) ?
You do find the maxium value in log time.
But I think it might be better, just to:
* first we find the max element
max_element = 0
max_index = 0
for k = alen(arr) to 1 step -1
if X >= arr(k)
max_element = arr(k)
max_index = k
endif
endfor
*This solution is much easier if I was programming in c/c++ where I could *use pointers. We'll wing it tho ;) Really, what I want to do is have a *pointer to the max_element and one to the min_element, and then if their *sum is greater then x, I decrease the max_element, if their sum is less *then X I increase the min_element, if their sum equal X I end. One final
*case, our end case, if max_element = min_element and max_ele + min_ele != *X, I return failure.
max_index = k
min_index = 1
do while arr(max_index)+arr(min_index) != X
if arr(max_index)+arr(min_index) > X
max_index = max_index - 1
else if arr(max_index)+arr(min_index) < X
min_index = min_index + 1
else if arr(max_index) = arr(min_index)&&we already know their sum doesn't
&&equal X, that's tested by our * &&our while loop
return "Failure!"
endif
enddo
Worst case, the entire array is scanned, or O(n) - linear running time.
im almost absolutely sure this works,
matt
>test = arr[int(k/2)]
>if X < test && We don't need to check the rest of the array
> test = arr[int(k/4))
> if X < test && we don't need to check 3/4 of the array
> ...
> endif
>endif
Previous
Next
Reply
View the map of this thread
View the map of this thread starting from this message only
View all messages of this thread
View all messages of this thread starting from this message only