# Find X in a partially sorted Array

Your job is to find the location (read index) of a given element X in an array gone through the following transformation process:

1. Take a fully sorted integer array of size N (N is known implicitly)
2. Take any random number of mutually exclusive even index pairs (as in that no index appears in more than 1 pair) from the array and swap the elements on those indexes.

A sample array can be like

[5, 2, 3, 4, -1, 6, 90, 80, 70, 100]


formed by

// Take fully sorted integer array
[-1, 2, 3, 4, 5, 6, 70, 80, 90, 100]
// Take some even index pairs : (0, 4) and (6, 8)
// Swap the elements in these indexes. i.e., element at 4<sup>th</sup> index goes to 0<sup>th</sup> etc.
// Final array:
[5, 2, 3, 4, -1, 6, 90, 80, 70, 100]


and a sample X to find in this array can be

-1


You should output the index of the element X in the final array (4 in the above example) or -1 if the element is not found in the array.

Rules

• In built searching functions are prohibited.
• You must write a method/function/program which takes input from STDIN/Command line arguments/Function arguments.
• Input must be in <Array> <X> format. Example: [5, 2, 3, 4, 1, 6, 9, 8, 7, 10] 1
• The input array may also contain duplicate integers. In such case, any one index can be the output. UPDATE : You may assume that total number of duplicates << (far less than) size of array. For the benefit of the question in general, duplicates are now prohibited to avoid playing a role in time complexity of the searching algorithm.
• Output should be the index of the element X in the array or -1 if not present.

Scoring

• Being a and a , your score is calculated by <byte count of your program>*<coeff. of complexity>
• Coefficient of Complexity is decided based on the worst case time complexity of your code (Big-O) using the mappings given below.
• If your code needs to know the length of the array, it can calculate length using inbuilt methods and that won't be added to the time complexity of the searching part of the code.
Time Complexity      Coefficient
--------------------------------
O(1)                 0.25
O(log(n))            0.5
O(n)                 5
O(n*log(n))          8.5
O(n^2)               10
O(greater than n^2)  20


Minimum score wins!

Bonus

• Multiply your final score by 0.5 if you can handle a case where the array has gone through the step 2 in the transformation process I times (instead of just 1), where I is passed as the third parameter in input.
• Note that while going through step 2, I times, pairs in each step are mutually exclusive, but pairs in different steps can have common indexes.

# JavaScript (E6) 97.5 (39*5*0.5)

(O(n), linear search, the array can be scrambled again and again)
The function accepts (and ignores) a third parameter

F=(a,x)=>a.map((e,i)=>e-x?0:j=i,j=-1)|j


or

F=(a,x)=>a.some((e,i)=>(j=i,e==x))?j:-1


or

F=(a,x)=>a.every((e,i)=>(j=i,e-x))?-1:j


Test in FireFox/FireBug console

F([5, 2, 3, 4, -1, 6, 90, 80, 70, 100],-1, 2)


Output

4

• Nicely played with coefficients and bonus! – Optimizer Oct 5 '14 at 8:32

# Golfscript, 20 * 2.5 = 50

~{={0:-1}*0):0}+%;-1


Explanation:

• ~ - eval the input. It should be in the form [-1 0 3 2 4] 3.
• {...}+% - prepend the last argument (needle) to {...}, then map the resulting function over the array
• ;-1 - discard the results of the mapping, and push -1 to the stack.

The real fun is what happens inside:

• = - check if the needle matches the haystack element
• {0:-1} - take the current value of the variable 0 and store it into the variable -1.
• * - execute the function n times = execute if the previous is true.
• 0):0 - increment the current value of 0.

yep. In golfscript, numeric all literals are just variables initialised to some useful values.

### Haskell, 51 * 2.5 = 127.5

a 0= -1;a x=x;f[]_= -1;f(h:t)n|h==n=0|1>0=a$1+f t n  ungolfed: adjust 0 = -1 adjust x = x find [] _ = -1 find (x:xs) n | x == n = 0 | otherwise = adjust$ 1 + find xs n


# Python 79.75 (319*0.5*0.5) 106.5 (213*0.5)

UPDATE: Since the time complexity is determined by worst case for any number of swaps, I have reduced my algorithm to work only for the case I=1, which results in O(log n) time.

The findX function is f, while g, and h are helpers.

The function uses the ordering of the odd indices to apply search to find where X should be. If X has been swapped then it uses a second binary to search to find where X has been swapped to, based on the value found at where X should have been. Since I use two binary searches in the worst case it is O(logN).

I find X by applying a binary search on the odd indices. If X is not found on the odd indices, I check the array at the even index where X should be if the array was ordered (call this value n1). If n1 equals X, I found the index. If n1 does not equal X I use the same binary search to find where n1 should be in the ordered array (to see if X was swapped with n1). Call this new value n2. If n2 equals X, I found the index. Otherwise I use the same binary search to find where n1 should be in the ordered array (to see if X was swapped with n2) ... etc.

The algorithm terminates when X is found or n1 is found a second time.

Essentially my algorithm traces the random swapping in reverse. That is, it will 'decode' the last swap, then 'decode' the second last swap, and so on until I decode the first swap. For each 'decode', I use a binary search ( O(logN) time ), plus an additional binary search to find the first index. The algorithm will 'decode' the simplest sequence of random swaps to get to the given state (e.g. the algorithm will not apply any decoding to an array that had the same swapping applied twice). Also, note that any sequence of swapping will be equivalent to a sequence of swapping of length less than or equal to N/2. Hence the complexity is at worst O(min(I, N/2) * logN) and the algorithm works for I swaps.

def f(l,X):
m=len(l)
i=g(l,X,0,m-m%2)
return -1 if i>=m else i if l[i]==X else g(l,l[i],0,m-m%2)
def g(l,X,n,m):
a=(n+m)//2
a+=a%2-1
return n if m<=n else g(l,X,a+1,m) if l[a]<X else g(l,X,n,a-1) if l[a]>X else a


def h(l,F,X,s,m): i=g(l,F,0,m-m%2) return -1 if i==s or i>=m else i if l[i]==X else h(l,l[i],X,s,m)

Ex:

print f([-1, 2, 3, 4, 5, 6, 70, 80, 90, 100],-1) print f([5, 2, 3, 4, -1, 6, 90, 80, 70, 100],-1) print f([5, 2, 3, 4, -1, 6, 90, 80, 70, 100], 5) print f([-1, 2, 70, 4, 90, 6, 3, 80, 5, 100],-1)

Output:

0 4 0 0 

• "I will find the index of X after I iterations." -- Iiiii'm not sure about that. Can you elaborate on that part? Still, very nice. – John Dvorak Oct 5 '14 at 2:44
• My bad, it will be at most I+1 iterations. I'll edit my post. – Cameron Oct 5 '14 at 2:52
• Your algorithm fails for e.g. f([1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1],2), which is a transformed version of f([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2],2). In fact, since an array consisting of an odd number of 1s followed by a 2 is guaranteed to contain no information in the odd indices, and the 2 may appear at any even index in the list, I've argued with @Optimizer above that sub-O(n) worst case performance is impossible. Otherwise, I had the same idea, hence props for a smooth implementation. ;) – COTO Oct 5 '14 at 3:13
• You're absolutely right about it only working for a single round of swaps. Two or more rounds of swaps allows all permutations of the even elements, meaning that (once again) the odd elements provide absolutely no information about the even elements in the worst case. Thus it is my contention that for I >= 2, it is impossible to beat O(n) worst case performance even with duplicates forbidden. – COTO Oct 5 '14 at 3:24
• @COTO are you sure two rounds of swaps are sufficient to generate every permutation? How do you generate larger cycles? Two rounds are definitely sufficient to randomise the lower half entirely (enough to force linear-time worst-case)by swapping all up, then all down, but then the permutation of the top half becomes entangled with the permutation of the bottom half (isomorphic cycle space, I believe). – John Dvorak Oct 5 '14 at 3:33

# JavaScript ES6, 95 (38*5*0.5)

Performs an O(n) search. Accepts bonus parameter but ignores it

f=(a,x)=>a.reduce((p,c,i)=>c-x?p:i,-1)

• Shouldn't f([1, 2, 3], 42) return -1? – Chiru Aug 9 '15 at 11:17
• @Chiru Yeah missed that part working on it – George Reith Aug 9 '15 at 11:17
• @Chiru Fixed unfortunately with more bytes – George Reith Aug 9 '15 at 12:41
• +1 for both fixing it and still having the shortest ES6 solution as of now. Great job! – Chiru Aug 9 '15 at 13:02