Find X in a partially sorted Array

Question

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 code-golf and a code-challenge, 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.

Answer 1

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

Answer 2

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.

Answer 3

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    

Answer 4

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

Answer 5

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)