OK, even if it isn't possible to cheaply extend the array by one, do this slight tweak for the same end result: store the last item in the array as a temporary,

OK, even if it isn't possible to cheaply extend the array by one, do this slight tweak for the same end result: store the last item in the array as a temporary, and replace it in the array by a sentinel value. (search the array). Once you find the value, if the index isn't that of the last entry, you've found it. If it is the last entry, check the temporary to see if it happened to be the value you were looking for. Finally, replace the last item in the array by the temporary value.