## Split

### December 30, 2011

Today’s exercise comes from our file of interview questions:

Given a list, return the first half of the list as one list and the second half of the list as a second list. For instance, given the input list {1 2 3 4}, output the two lists {1 2} and {3 4}. If the input list has an odd number of items, the middle item can go to either list, so that the input list {1 2 3 4 5} can result in the output lists {1 2} and {3 4 5} or the output lists {1 2 3} and {4 5}.

Your task is to write the function that splits a list in two halves. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 16 Responses to “Split”

1. Bogdan Popa said

Simple enough in Python:

```def split(L):
median = int(len(L) / 2)
return L[:median], L[median:]
```
2. Tante Hedwig said

Even simpler in Haskell:

spl xs = splitAt (length xs `div` 2) xs

3. ardnew said

this isn’t one of perl’s more elegant applications.

as far as I know, perl does not allow you to return multiple lists. instead, we return a list of list references. this has the requirement of allocating our half-lists from the calling routine, and passing references to those half-lists to our hsplit routine:

```use strict;
use warnings;

sub hsplit(\$\$\$)
{
my \$n = scalar @{\$_[0]};
my \$m = int(\$n / 2);

@{\$_[1]} = @{\$_[0]}[0  .. \$m - 1];
@{\$_[2]} = @{\$_[0]}[\$m .. \$n - 1];

return (\$_[1], \$_[2]);
}

#
# usage example
#
my @list = (1,2,3,4,5);
my @ll = ();
my @lr = ();

hsplit(\@list, \@ll, \@lr);

print "left  = @ll\n";
print "right = @lr\n";
```
4. ardnew said

whoops, no need for that return statement at the end of hsplit.

5. Ikenna said

def split(aList):
cut = len(aList) / 2
firstH = aList[:cut]
secondH = aList[cut:]
return firstH,secondH

6. takacsv said

Oneliner solution in perl, basic tests included:

http://pastebin.com/GtduSYTg

7. hc5duke said
```def split(a)
[ a[0..a.length/2], a[a.length/2..-1] ]
end
```

or if you:

```class Array
def split
[ self[0, length/2], self[length/2..-1] ]
end
end
```

you can do

```> [1, 2, 3, 4, 5].split
=> [[1, 2], [3, 4, 5]]
```
8. hc5duke said

Oops, I meant to say it’s ruby… Another way with the second approach:

```class Array
def split
[ first(length/2), slice(length/2..-1) ]
end
end
```

Another Perl solution. Works for empty and single-element lists as well.

```sub splitlist {
my \$mid = @_ / 2 -1 ;
\$mid = 0 if \$mid < 0 && @_;
return [@_[0 .. \$mid]], [@_[\$mid+1 .. @_-1]];
}
```
10. Axio said

Handles empty list and single element lists as well.

```(define (split-at l n)
(let loop ((n n) (h '()) (t l))
(if (zero? n)
(values (reverse h) t)
(loop (1- n) (cons (car t) h) (cdr t)))))

(define (split l)
(let ((size (length l)))
(split-at l (quotient size 2))))
```
11. Clojure example:

(defn split [lst]
(let [half-count (int (/ (count lst) 2))]
[(take half-count lst) (drop half-count lst)]))

12. ```(define (split xs)
(let-values (((a b)
(split-at-right xs (round (/ (floor (length xs)) 2)))))
(displayln a) (displayln b)))

(split '(1 2 3 4 5))
```
13. Jussi Piitulainen said

Python to split a pair chain with the slow and fast enumeration of the elements as in the reference problem and solution.
Pairs are (tail, head), so they look backwards when printed, but they match Python’s reduce which accumulates from left.

```from functools import reduce

def each(xs, *, head = True):
while xs: yield xs[bool(head)] ; xs = xs[0]

def even(xs, *, head = True):
while xs: yield xs[bool(head)] ; xs = xs[0] and xs[0][0]

def split(cs):
left, rest = None, None
for head, tail, fast in zip(each(cs), each(cs, head = False), even(cs)):
left, rest = (left, head), tail
return reduce(pair, each(left), None), rest
```

For testing, a mapping from Python lists to pair chains and back.

```def unlist(xs): return reduce(pair, reversed(xs), None)
def relist(xs): return list(each(xs))

def test(xs):
left, rest = split(unlist(xs))
print(list(xs), '=', relist(left), '+', relist(rest))
```

Sourcecode tag, please work.

14. DGel said

C++ solution. A bit verbose, but well it’s c++ :) No need for the tortoise and hare solution, as the length of the list is already known.

```
#include <vector>
#include <utility>

template <typename T>
std::pair<std::vector<T>, std::vector<T> > split_list(std::vector<T> &list)
{
size_t middle = list.size()/2;
std::vector<T> first(list.begin(), list.begin() + middle);
std::vector<T> second(list.begin() + middle, list.end());
return std::pair<std::vector<T>, std::vector<T> >(first, second);
}

```
```