If I have an array of unsorted numbers and a number I'm looking for, I believe there's no way of checking if my number is in it except by going through each member and comparing.
Now, in mathematics and various theoretical branches I've been interested in, there's often the pattern that you usually get what you put in. What I mean is, there's usually an explanation for every unexpected result. Take the Monty Hall problem as an example. It seems counter-intuitive until you realize the host adds more information into the situation because he knows what door the car is behind.
Since you're iterating on the array, instead of just getting a yes or no answer, you also get the exact location of the element (if it's there). Wouldn't it then make sense that there's an algorithm that's less complex, but give you ONLY a single bit of information?
Am I completely off base here?
Is there an actual correlation between the amount of information you get and the complexity of an algorithm? What's the theory behind the relationship between the amount of information you get from an algorithm and it's complexity?
When you are searching an array, indexing is the price that you pay for having an array. An ability to access an element by index is inherent in the structure of the array: in other words, once you say "I am going to search an array" (not a collection, but specifically an array) you have already paid for the index. At this point, there is no way to get rid of it, and the O(n) cost associated with searching the array.
However, this is not the only solution: if you agree to drop the ability to index as a requirement, you could build a collection that gives you a yes/no answer much faster. For example, if you use a hash table, your search time becomes O(1). Of course there is no associated index in a hash table: inability to access items in arbitrary order is your payment for an ability to check for presence or absence of items in constant time.