Searching

A searching algorithm is an algorithm that aims to find an item within a collection of items.

There are many kinds of searching algorithms, including:

• list search algorithms, which search for an item in a linear (one-dimensional) collection, for example, an array.
  • linear search, searches any list, runs in O(n). Typically a search like this would use a loop to iterate through the list until the required item was found.
  • binary search, searches a sorted list, runs in O(log n).
• tree searching algorithms, which search for an item in a tree.
• string searching algorithms, which search for patterns within strings

Bash

function in_array {
   for i in "${@:2}"; do
      [[ "$i" == "$1" ]] && return 0
   done
} 

haystack=("apple" "orange" "yellow banana")
in_array "orange" "${haystack[@]}" && echo found || echo not found

Go

func in_array(needle interface{}, haystack []interface{}) (exists bool) {
   for i := range haystack {
      if exists = haystack[i] == needle; exists {
         return
      }
   }
   return
}

Java

Java implements the binary search in both the Collections and Arrays classes.

• java.util.Collections
• java.util.Arrays

JavaScript

From all modern browsers and IE9+ you can use Array.prototype.indexOf():

var present = haystack.indexOf(needle) > -1;

You can either polyfill the standard function with the above mentioned MDN article on indexOf() or use a simpler version:

function in_array(needle,haystack) {
	if(!haystack instanceof Array) throw 'Error: Haystack isn\'t an array.';
	for(var i in haystack) if(haystack[i]==needle) return true;
	return false;
}

Or if you use jQuery anyways:

var present = $.inArray(needle, haystack) > -1;

Perl

if(grep $_ eq $needle, @haystack) {
	print "Success!";
}

See Also

• Trees
• Sorting