Sorted Arrays and Search

I came across this article yesterday: Efficiently Searching a Sorted Array. If you haven't heard about Four Guys from Rolla yet, you haven't been programming long enough. I come across them every now and then. Good stuff.

What I learned:

In order to search a sorted array efficiently, the array has to be sorted first (Duh!). Sorting an array is a linear operation which isn't ideal; it works out to be O(n). I may be wrong on this as I can't find my source any more. Ugh.