Little thinking on problem 'Searching an Element in an Array'

This is the most common topic in DS/Algo. When anyone tries to touch DS/Algorithm boundaries to get into it, I believe this is the first Problem which comes into picture. Let's realize it a little. Problem is very clear in its statement - Search an element in an array. From the Best Algorithm perspective the solution should be in terms of minimum complexity.

 Now if we talk about complexity, I think here it will depend mainly on below: (May be some other can also be included)

1. Number of elements in an array. (With this it will be decided whether it will vary based on length of the input given.)
2. Number of comparison we are making. (With this it will be decided that it will vary based on the data given in Input Array. )

 If we remind, mostly everyone have started with 2 Algorithms: Linear and Binary Search. I will not explain mechanism here as everyone knows at least this. These 2 are fulfilling above 2 points one by one. Here best one is Binary Search because this can give result in very less comparisons.

This is the time to think. Let's come to the real life problems and try to see around ourselves. For example: If we are looking a candidate with Name XXX in a class, can we use Binary search. Or looking for an English Word in Newspaper or simply in paragraph etc. How many times we are getting the situation where it will be similar to finding a word in a dictionary or chapter in an index. Taking an assumption of having a ordered input for a search is very difficult normally to proceed.

 Now in this situation, if we attempt to make it ordered and then look for our candidate, it will be more complex than the straightforward approach (Sort + Search). So isn't it, we should focus on finding an finding a best way where there will be no restriction on Input.

 If we see alternative to Binary search, there are multiple search algorithms available, which can give you even better complexity. For example: Exponential Search, Jump Search, Interpolation search etc. But do we know the way we can reduce the complexity for Linear search. Or in other terms, Minimum Complexity to search an elements in an array when Inputs are not in sorted order. Can it be reduced from n ?

 Now here as we know if inputs will not be sorted, we will have to compare element with every element so it will be difficult to reduce number of comparisons but we can think in some other areas. For example: we can think in terms of time, Like whether some things can be done in parallel and time can be saved etc.