How can I check if a string is in an array without iterating over the elements?

Question

Is there a way of checking if a string exists in an array of strings - without iterating through the array?

For example, given the script below, how I can correctly implement it to test if the value stored in variable $test exists in $array?

array=('hello' 'world' 'my' 'name' 'is' 'perseus')

#pseudo code
$test='henry'
if [$array[$test]]
   then
      do something
   else
      something else
fi

Note

I am using bash 4.1.5

I'm 100% positive an identical question already exists here. Haven't found it yet, though. — Charles Duffy, Jul 09 '12 at 14:14
http://stackoverflow.com/questions/3685970/bash-check-if-an-array-contains-a-value — Misch, Jul 09 '12 at 14:14
@CharlesDuffy: this may be the one you are referring to: http://stackoverflow.com/questions/3685970/bash-check-if-an-array-contains-a-value However, I don't like the solution for two reasons: 1. It involves iterating over the array, 2. A custom function must be written. I would prefer to use 'inbuilt' bash function(s) — Homunculus Reticulli, Jul 09 '12 at 14:16
@HomunculusReticulli Oh. If you want only builtins, the answer is "no, you can't do that" -- and you should have specified it in your question. — Charles Duffy, Jul 09 '12 at 14:16
...well, let's be clearer -- you can't come up with a non-iterative solution _without using associative arrays_. — Charles Duffy, Jul 09 '12 at 14:18
@CharlesDuffy: Not sure how I could have made my self more clear in the question. I stated: **without iterating through the array** the solution you offered does involve iterating through the array - if there is no inbuilt way of doing this, then that solution will have to do. — Homunculus Reticulli, Jul 09 '12 at 14:19
Not without iterating, but it is a very simple function to make: `lookup() { s="$1"; shift; for i; do [[ "$s" = "$i" ]] && return 0; done; return 1; }` — fork0, Jul 09 '12 at 14:19
@HomunculusReticulli "More clear" would have been putting it in the title. Where it is, now. — Charles Duffy, Jul 09 '12 at 14:21
While I can see why you might not want to iterate, I can't imagine why you'd want to avoid functions. They're part of well-structured code. — Dennis Williamson, Jul 09 '12 at 14:28
@DennisWilliamson: I'm new to bash (as you can prob. tell from some of my questions), so I want to use as many of the intrinsic functionality/features as possible, before resorting to "rolling my own" - which will invariably be more buggy. — Homunculus Reticulli, Jul 09 '12 at 14:32
@HomunculusReticulli what solution to this did you use ? I feel like I am missing that magic duh one liner for this and I definitely don`t see it here . — Tegra Detra, Jun 28 '14 at 07:44
@CharlesDuffy stop declaring whats "Not Possible" it`s particularly un helpful and much different then saying "I don`t know how to do it ". — Tegra Detra, Jun 28 '14 at 07:50
@JamesAndino, there are only so many ways to do O(1) lookups included in bash's implementation. (Your own answer doesn't exercise any of them, and so is in fact iterative). "Not possible" _does_ make some assumptions, when spoken about a continually-evolving language, but I'm still willing to call the ground I stand on fairly solid. (Building and applying a regex is another approach I hadn't thought of -- but while the application of a previously-compiled regular expression is non-iterative, building the regex from an array is also an iterative process). — Charles Duffy, Jun 28 '14 at 13:50
i just have this buggards feeling there is a way to do this in a one liner every one forgot about — Tegra Detra, Jun 28 '14 at 14:17
@JamesAndino, there may well be a one-liner we haven't collectively thought of, but a one-liner that isn't iterative in nature (even by way of a parameter expansion that loops)? I'd literally place money on its nonexistence. — Charles Duffy, Aug 18 '15 at 17:25

Charles Duffy · Accepted Answer · 2017-07-17T17:11:45.600

17

With bash 4, the closest thing you can do is use associative arrays.

declare -A map
for name in hello world my name is perseus; do
  map["$name"]=1
done

...which does the exact same thing as:

declare -A map=( [hello]=1 [my]=1 [name]=1 [is]=1 [perseus]=1 )

...followed by:

tgt=henry
if [[ ${map["$tgt"]} ]] ; then
  : found
fi

edited Jul 17 '17 at 17:11

answered Jul 09 '12 at 14:18

Charles Duffy

280,126
43
390
441

But strictly speaking (despite of the name) an "associative array" is not an array, but a hash table. For a pure array there is no alternative to expecting half of the items on average to find out whether a specific item is present in the array. The other alternative would be sorting the array (a real array this time) and doing a binary search. Then you would have to inspect at most log2(number_of_items). – U. Windl Nov 08 '22 at 13:30
@U.Windl, bash doesn't _have_ things that are pure arrays. Numerically-indexed "arrays" are _also_ maps in bash; they're just maps where the only allowed keys are integers. (That's why they're allowed to be sparse, and why `arr=( [1500]="hi" )` is just as memory-efficient as `arr=( [0]="hi" )`) – Charles Duffy Nov 08 '22 at 16:32
Didn't know that works with `declare -a` arrays; I thought it requires `declare -A` arrays, thus switching to associative arrays (hash table). – U. Windl Nov 09 '22 at 07:48
@U.Windl, regular `declare -a` arrays are absolutely sparse (and implemented as hash tables under the hood). Try it yourself. – Charles Duffy Nov 09 '22 at 16:15

Todd A. Jacobs · Answer 2 · 2012-07-09T14:53:14.643

There will always technically be iteration, but it can be relegated to the shell's underlying array code. Shell expansions offer an abstraction that hide the implementation details, and avoid the necessity for an explicit loop within the shell script.

Handling word boundaries for this use case is easier with fgrep, which has a built-in facility for handling whole-word fixed strings. The regular expression match is harder to get right, but the example below works with the provided corpus.

External Grep Process

array=('hello' 'world' 'my' 'name' 'is' 'perseus')
word="world"
if echo "${array[@]}" | fgrep --word-regexp "$word"; then
    : # do something
fi

Bash Regular Expression Test

array=('hello' 'world' 'my' 'name' 'is' 'perseus')
word="world"
if [[ "${array[*]}" =~ (^|[^[:alpha:]])$word([^[:alpha:]]|$) ]]; then
    : # do something
fi

"Always" is a bit strong. Associative array lookups are O(1), not O(n). — Charles Duffy, Jun 28 '14 at 13:50
@CharlesDuffy O(1) at best [depending on the underlying implementation](https://en.wikipedia.org/wiki/Associative_array#Comparison). — Jens, Jun 23 '22 at 01:39

Dennis Williamson · Answer 3 · 2014-01-20T21:52:38.930

4

You can use an associative array since you're using Bash 4.

declare -A array=([hello]= [world]= [my]= [name]= [is]= [perseus]=)

test='henry'
if [[ ${array[$test]-X} == ${array[$test]} ]]
then
    do something
else
    something else
fi

The parameter expansion substitutes an "X" if the array element is unset (but doesn't if it's null). By doing that and checking to see if the result is different from the original value, we can tell if the key exists regardless of its value.

edited Jan 20 '14 at 21:52

answered Jul 09 '12 at 14:18

Dennis Williamson

346,391
90
374
439

Think I beat you by... 25 seconds? :) – Charles Duffy Jul 09 '12 at 14:18
@DennisWilliamson: This is the kind of approach I was hoping for. Will this work for any bash array. See my previous question (http://stackoverflow.com/questions/11395776/bash-string-interpolation) to see how I am building my array. If your solution works for all bash array types (can't see why not), then this is my preferred solution. – Homunculus Reticulli Jul 09 '12 at 14:23
@HomunculusReticulli: It only works for associative arrays (or regular arrays if you're testing for the presence of a numeric index). – Dennis Williamson Jul 09 '12 at 14:34
@HomunculusReticulli: I would write the whole thing in Python. – Dennis Williamson Jul 09 '12 at 14:37
@CharlesDuffy: You did beat me slightly, but you're using the dreaded iteration to build the initial array. ;-) – Dennis Williamson Jul 09 '12 at 14:39
2

This is completely pedantic, but I want to point out that associative arrays still perform iteration at the implementation level. The shell programmer just doesn't have to manually implement the indexing operation. :) – Todd A. Jacobs Jul 09 '12 at 15:01
@CodeGnome, eh? They're implemented with hash tables. – Charles Duffy Jun 28 '14 at 13:55
In my case, I _had_ to assign a value: `[hello]=0` worked whereas `[hello]=` did not. – Jens Jun 23 '22 at 01:36
@Jens: What happened without the value? What version of Bash? – Dennis Williamson Jun 23 '22 at 18:59
@DennisWilliamson: that’s with bash v5.1.16: elements `["foo"]=` would fail the lookup `[[ ${array["$test"]} ]]`. – Jens Jun 23 '22 at 21:09
1

@Jens: That's a different test. In mine, the `-X` sets a default if the element is unset. – Dennis Williamson Jun 23 '22 at 22:34

Bernard · Answer 4 · 2014-06-28T14:22:57.837

2

array=('hello' 'world' 'my' 'name' 'is' 'perseus')
regex="^($(IFS=\|; echo "${array[*]}"))$"

test='henry'
[[ $test =~ $regex ]] && echo "found" || echo "not found"

edited Jun 28 '14 at 14:22

answered Mar 26 '14 at 10:29

Bernard

16,149
12
63
66

Build the regex from the array, and I think you'd have a winner here. – Charles Duffy Jun 28 '14 at 13:49
@Charles-Duffy: Updated with the regex – Bernard Jun 29 '14 at 10:12
Not particularly generalized as-is -- need to escape any array contents during expansion, lest the array contain anything that doesn't match itself directly as a regex. One way to do this, though involving some performance hit: `requote() { sed 's/[^^]/[&]/g; s/\^/\\^/g' <<< "$1"; }` – Charles Duffy Jun 29 '14 at 15:57

Fred Astair · Answer 5 · 2015-04-29T11:02:16.907

Reading your post I take it that you don't just want to know if a string exists in an array (as the title would suggest) but to know if that string actually correspond to an element of that array. If this is the case please read on.

I found a way that seems to work fine .

Useful if you're stack with bash 3.2 like I am (but also tested and working in bash 4.2):

array=('hello' 'world' 'my' 'name' 'is' 'perseus')
IFS=:     # We set IFS to a character we are confident our 
          # elements won't contain (colon in this case)

test=:henry:        # We wrap the pattern in the same character

# Then we test it:
# Note the array in the test is double quoted, * is used (@ is not good here) AND 
# it's wrapped in the boundary character I set IFS to earlier:
[[ ":${array[*]}:" =~ $test ]] && echo "found! :)" || echo "not found :("
not found :(               # Great! this is the expected result

test=:perseus:      # We do the same for an element that exists
[[ ":${array[*]}:" =~ $test ]] && echo "found! :)" || echo "not found :("
found! :)               # Great! this is the expected result

array[5]="perseus smith"    # For another test we change the element to an 
                            # element with spaces, containing the original pattern.

test=:perseus:
[[ ":${array[*]}:" =~ $test ]] && echo "found!" || echo "not found :("
not found :(               # Great! this is the expected result

unset IFS        # Remember to unset IFS to revert it to its default value

Let me explain this:

This workaround is based on the principle that "${array[*]}" (note the double quotes and the asterisk) expands to the list of elements of array separated by the first character of IFS.

Therefore we have to set IFS to whatever we want to use as boundary (a colon in my case):
```
IFS=:
```
Then we wrap the element we are looking for in the same character:
```
test=:henry:
```
And finally we look for it in the array. Take note of the rules I followed to do the test (they are all mandatory): the array is double quoted, * is used (@ is not good) AND it's wrapped in the boundary character I set IFS to earlier:
```
[[ ":${array[*]}:" =~ $test ]] && echo found || echo "not found :("
not found :(
```

If we look for an element that exists:

test=:perseus:
[[ ":${array[*]}:" =~ $test ]] && echo "found! :)" || echo "not found :("
found! :)

For another test we can change the last element 'perseus' for 'perseus smith' (element with spaces), just to check if it's a match (which shouldn't be):
```
array[5]="perseus smith"
test=:perseus:
[[ ":${array[*]}:" =~ $test ]] && echo "found!" || echo "not found :("
not found :(
```
Great!, this is the expected result since "perseus" by itself is not an element anymore.
Important!: Remember to unset IFS to revert it to its default value (unset) once you're done with the tests:
```
unset IFS
```

So so far this method seems to work, you just have to be careful and choose a character for IFS that you are sure your elements won't contain.

Hope it helps anyone!

Regards, Fred

I know I'm late to the party, but I'd like to add that the "[ascii unit separator](https://en.wikipedia.org/wiki/Unit_separator)" is a good candidate for the IFS to use :-) That is exactly what this non-printable character was invented for. To type it in vim press Ctrl+V followed by 031. I like to assign it to a readonly variable and use that when I need it. — markgraf, Aug 24 '19 at 19:24

score 2 · Answer 6 · answered May 06 '20 at 04:02

2

In most cases, the following would work. Certainly it has restrictions and limitations, but easy to read and understand.

if [ "$(echo " ${array[@]} " | grep " $test ")" == "" ]; then
    echo notFound
else
    echo found
fi

answered May 06 '20 at 04:02

newbie

21
1

hrez · Answer 7 · 2014-01-26T15:25:50.073

Instead of iterating over the array elements it is possible to use parameter expansion to delete the specified string as an array item (for further information and examples see Messing with arrays in bash and Modify every element of a Bash array without looping).

(
set -f
export IFS=""

test='henry'
test='perseus'

array1=('hello' 'world' 'my' 'name' 'is' 'perseus')
#array1=('hello' 'world' 'my' 'name' 'is' 'perseusXXX' 'XXXperseus')

# removes empty string as array item due to IFS=""
array2=( ${array1[@]/#${test}/} )

n1=${#array1[@]}
n2=${#array2[@]}

echo "number of array1 items: ${n1}"
echo "number of array2 items: ${n2}"
echo "indices of array1: ${!array1[*]}"
echo "indices of array2: ${!array2[*]}"

echo 'array2:'
for ((i=0; i < ${#array2[@]}; i++)); do 
   echo "${i}: '${array2[${i}]}'"
done

if [[ $n1 -ne $n2 ]]; then
   echo "${test} is in array at least once! "
else
   echo "${test} is NOT in array! "
fi
)

score 0 · Answer 8 · answered Jun 28 '14 at 07:46

0

q=( 1 2 3 )
[ "${q[*]/1/}" = "${q[*]}" ] && echo not in array || echo in array 
#in array
[ "${q[*]/7/}" = "${q[*]}" ] && echo not in array || echo in array 
#not in array

answered Jun 28 '14 at 07:46

Tegra Detra

24,551
17
53
78

This answer is both iterative (how do you think `${foo[@]/bar/}` works?) and inaccurate (not distinguishing between `(1 "2 3" 4)` and `(1 2 3 4)`) – Charles Duffy Jun 28 '14 at 13:48
The replacement happens per array entry then concats them instead of concats them and does a replacement, I checked ( thats not to say this is not a terrible way to do this ) . – Tegra Detra Jun 28 '14 at 14:17
Correct -- replaces per entry, then concats. So, if you're trying to test whether `2` is an entry, you wouldn't want `2 3` to be modified, which in this case it would be. – Charles Duffy Jun 28 '14 at 19:23

David C. Rankin · Answer 9 · 2019-04-20T19:56:53.113

0

#!/bin/bash

test="name"

array=('hello' 'world' 'my' 'yourname' 'name' 'is' 'perseus')
nelem=${#array[@]}
[[ "${array[0]} " =~ "$test " ]] || 
[[ "${array[@]:1:$((nelem-1))}" =~ " $test " ]] || 
[[ " ${array[$((nelem-1))]}" =~ " $test" ]] && 
echo "found $test" || echo "$test not found"

Just treat the expanded array as a string and check for a substring, but to isolate the first and last element to ensure they are not matched as part of a lesser-included substring, they must be tested separately.

edited Apr 20 '19 at 19:56

answered Jun 28 '14 at 08:02

David C. Rankin

81,885
6
58
85

You can super easily have false positives with this and if your array had word boundaries in an entry you could`t even craft a regex you could be sure worked – Tegra Detra Jun 28 '14 at 08:11
That ought to tighten it up a bit. – David C. Rankin Jun 28 '14 at 08:22
Could you walk through ```[[ "${array[@]}" =~ "${i:0:$((${#test}))}" ]]``` , where is the i coming from ? – Tegra Detra Jun 28 '14 at 10:52
Should be no i in the present answer. I tested with a loop and without. Copied the wrong line :p – David C. Rankin Jun 28 '14 at 11:31
Now Im really gonna bug you ... ```q=( 2 'x x' 3 ); [[ "${q[@]}" =~ " x " ]] && echo ok # ok``` , but don`t feel bad I've been up 2 days straight figuring every stupid thing about bash I can . – Tegra Detra Jun 28 '14 at 12:15
Touche~ That case I grant you will produce a substring match of 'x x'. The regex solution is the only loop free way to prevent against all corner cases, but it you are working with multi-line solutions, you might as well use a loop: `for i in "${array[@]}"; do test "${i:0:$((${#test}))}" == "$test" && echo "found: $i"; done` – David C. Rankin Jun 28 '14 at 19:12
If I put `test="hello"`, The output is wrong "hello not found" – Calvin Duy Canh Tran Apr 20 '19 at 19:24
1

@CalvinDuyCanhTran - remove the spaces from `[[ "${array[@]}" =~ " $test " ]]` to make `[[ "${array[@]}" =~ "$test" ]]` to match the string without whitespace. – David C. Rankin Apr 20 '19 at 19:35
@CalvinDuyCanhTran - thank you for catching that. The first and last element of the array must be treated separately (they will have no leading and trailing space, respectively) – David C. Rankin Apr 20 '19 at 19:57

score 0 · Answer 10 · answered Dec 01 '21 at 14:00

0

if ! grep -q "$item" <<< "$itemlist" ; then .....

Should work fine.

answered Dec 01 '21 at 14:00

John

1

1

Welcome to SO, Could you add more explanation to your answer please. – YLR Dec 01 '21 at 14:48
But grep will always inspect all items, even if you don't see it! – U. Windl Nov 08 '22 at 13:32

jficz · Answer 11 · 2022-04-25T18:06:06.573

0

for simple use cases I use something like this

array=( 'hello' 'world' 'I' 'am' 'Joe' )
word=$1

[[ " ${array[*]} " =~ " $word " ]] && echo "$word is in array!"

Note the spaces around ". This works as long as there are no spaces in the array values and the input doesn't match more values at once, like word='hello world'. If there are, you'd have to play with $IFS on top of that.

edited Apr 25 '22 at 18:06

answered Apr 25 '22 at 18:01

jficz

271
3
8

How can I check if a string is in an array without iterating over the elements?

11 Answers11

External Grep Process

Bash Regular Expression Test

Let me explain this:

Linked