Find $i$-th number in unsorted sequence in logspace (deterministic turing machine)

Question

There is given input - words is sequence of numbers: $w_i$ is number in sequence, $i$ is position. All of them are in written in binary system.

$$w_1\#,...\#w_k\#i$$ Prove that there exists deterministic Turing machine which find $i$-th number in sorted sequence $w$ in logspace.

I am not sure if I correctly solved it, so I ask for checking my reasoning. It seems to be fairly simple.

First of all, what we can do in logspace:
compare two numbers
iter over sequence (move to $n$-th number)

Simply, we consider one by one each element of sequence and count how many elements is less than currently considered. If we count $i-1$ numbers, then we stop. It requires logarythmic($k$) memory for counter. These counter can be reused (for each iteration).

Waht do you think ? Maybe some other approach to proving it ?

Answer 1

First let's consider the case when numbers are unique. The idea is that for each element $w_t$ we count the number of elements in the sequence which are less than $w_t$. After each loop on all elements of the sequence we check if there are $i-1$ elements less than $w_t$ then $w_t$ must be $i$-th element in the sorted sequence, so we halt with the output equal to $w_t$.

proc(w, k, i)
 for t=0 to k
   counter = 0
   for j=0 to k
     if w[t] > w[j]
      counter = counter + 1
   if counter == i-1 then output w[t] and halt 
end-proc  

Now, if numbers are not unique then we have to count duplicates as well

proc(w, k, i)
 for t=0 to k
   counter = 0
   dups = 0
   for j=0 to k
    skip if j == t
    if w[t] == w[j]
      dups = dups + 1
   for j=0 to k
     if w[t] > w[j]
       counter = counter + 1
   if counter+1 <= i AND i <= counter + dups+1 
     then output w[t] and halt 
end-proc 

  w[1] w[2] ... w[counter] w[t] w[t] ... w[t] ..
  \__________  __________/     \_____  ____/    
             \/                      \/
 all elements less than w[t]   duplicates        

Both procedures require only constant number of variables i, j, k, counter, and dups whose lengths are $O(\log(k))$. Your solution is similar to these algorithms so your approach is correct.

Answer 2

Maintain 3 registers, A, B, C. For the first two have them be "the Ath number is located at index B". The third register, use it to find the next largest number. Psuedo:

A = 1
B = the index of the smallest element in the sequence
C = number of elements equal to W[B]
A += C
while (A < I) {
  C = index of smallest element larger than W[B]
  B = C
  A += 1
  C = number of elements equal to W[B]
  A += C
}
output B

The main idea is that the entire procedure can be carried out with a constant number of pointers (you may need pointers for the subroutines also, but the amount doesn't depend on the input). Constant number of pointers and never copying any of the data from the list results in logspace.