Fundamental Use
Once upon a time, most computer time was spent on sorting, and the majority of the rest on searching. I’d say thats probably close to true today, as even browsing the web is, at its most basic an act of searching. Seeing as i’ve covered the sorting side of things, I thought i’d talk about the “other half”.
I’ve touched on searching for items as it applies to looking for an item in a tree or a hash table, but in this article i am going to talk about how it applies to arrays and to some extent to linked lists – linear data structures if you will.
Their are two classical approaches to sorting linear collections: the aptly named linear search, and the binary search algorithm.
Linear Search
The Linear Search algorithm is the simplest way to search an array, and (unfortunately) the ONLY way to search a linked list. It is very simple to implement with a loop, starting with the first item in the list you check if it is the item your searching for, and if it is, your done, otherwise continue with next item in the list so on and so forth till you find what your searching for or run out of items to check (search failure).
While being easy to implement, Linear search has as the name would imply, linear time complexity, requiring or O(n) for those of you speaking big-Oh.
Binary Search
Seeing as on vey large data sets that O(n) complexity can be serious bottleneck in performance, better algorithms have been devised. The most popular searching algorithm is binary search, which performs in O(log n) time. Binary search comes with two caveats: It only works it the data is in sorted order and it requires random access to the container, so linked lists are out.
The binary search algorithm is analgous to searching a binary search tree: you compare the item your searching to the middle item on the list, if it is the item your looking for return, other wise if it is less than the middle item, you cut the list in half and search the bottom half of the list, or if its greater, you search the top half.
The algorithm can be implemented easily both recursively and iteratively, i will demonstrate the iterative approach below:
This algorithm returns the array index of the item your searching for, or -1 if the item isn’t present.
