bash script: different results when called with or without sudo

Every script begins with a Shebang, without it the shell starting your script doesn't know which interpreter should run your script¹ and might – as in the case of sudo ./script.sh here – run it with sh, which in Ubuntu 16.04 is linked to dash. The conditional expression [[ is a bash compound command, so dash doesn't know how to handle it and throws the error you encountered.

The solution here is to add

#!/bin/bash

as the first line of your script. You may get the same result when you call it explicitly with sudo bash ./script.sh, but a shebang is the way to go.
To check which shell runs your script, add echo $0 to it. That's not the same as echo $SHELL, citing wiki.archlinux.org:

SHELL contains the path to the user's preferred shell. Note that this is not necessarily the shell that is currently running, although Bash sets this variable on startup.

1: As you started ./test.sh with bash it just assumed bash, the same goes for the sudo su subshell.

As @dessert explained, the problem here is that your script doesn't have a shebang line. Without a shebang, sudo will default to attempting to run the file using /bin/sh. I couldn't find it documented anywhere, but I confirmed by checking the sudo source code where I found the following in the file pathnames.h:

#ifndef _PATH_BSHELL
#define _PATH_BSHELL "/bin/sh"
#endif /* _PATH_BSHELL */

This means "set if the variable _PATH_BSHELL isn't defined, set it to /bin/sh". Then, in the configure script included in the source tarball, we have:

for p in "/bin/bash" "/usr/bin/sh" "/sbin/sh" "/usr/sbin/sh" "/bin/ksh" "/usr/bin/ksh" "/bin/bash" "/usr/bin/bash"; do
    if test -f "$p"; then
    found=yes
    { $as_echo "$as_me:${as_lineno-$LINENO}: result: $p" >&5
$as_echo "$p" >&6; }
    cat >>confdefs.h <<EOF
#define _PATH_BSHELL "$p"
EOF

    break
    fi
done

This loop will look for /bin/bash, /usr/bin/sh, /sbin/sh, /usr/sbin/sh or /bin/ksh and then sets the _PATH_BSHELL to whichever was found first. Since /bin/sh was the first in the list and it exists, _PATH_BSHELL is set to /bin/sh. The result of all this is that the default shell of sudo unless otherwise defined is /bin/sh.

So, sudo will default to running things using /bin/sh and, on Ubuntu, that is a symlink to dash, a minimal POSIX compliant shell:

$ ls -l /bin/sh
lrwxrwxrwx 1 root root 4 Feb 27  2015 /bin/sh -> dash

The [[ construct is a bash feature, it isn't defined by the POSIX standard and isn't understood by dash:

$ bash -c '[[ true ]] && echo yes'
yes
$ dash -c '[[ true ]] && echo yes'
dash: 1: [[: not found

In detail, in the three invocations you tried:

1. ./test.sh

   No sudo; in the absence of a shebang line, your shell will try to execute the file itself. Since you are running bash, this will effectively run bash ./test.sh and work.

2. sudo su followed by ./test.sh.

   Here, you are starting a new shell for the user root. This will be whatever shell is defined in the $SHELL environment variable for that user and, on Ubuntu, root's default shell is bash:

   $ grep root /etc/passwd
   root:x:0:0:root:/root:/bin/bash
   

3. sudo ./test.sh

   Here, you are letting sudo execute the command directly. Since its default shell is /bin/sh as explained above, this causes it to run the script with /bin/sh, which is dash and it fails since dash doesn't understand [[.

_{Note: the details of how sudo sets the default shell seem to be a bit more complex. I tried changing the files mentioned in my answer to point to /bin/bash but sudo was still defaulting to /bin/sh. So there must be some other places in the source code where the default shell is defined. Nevertheless, the main point (that sudo defaults to sh) still stands.}