Why searching in an array takes constant time? Anyway we have to visit every entry for searching.?

Answer 1

Are you meaning searching yahoo! Answers? Your question is hard to understand. try to rephrase it and we'll see what answer we can come up with. Good luck

Answer 2

In fact, it usually *doesn't* take "constant" time - "constant time" means it takes the same amount of time no matter *how* many you need to search through - 1, 10, or a million. Most simplistic array searches take what is known as O(n) time - which means the time taken is proportional to the number of entries to search. 20 takes twice as long as 10, and so on.

If you can afford the added overhead of keeping the array sorted, you can probably get it down to O(log n) - which means it's proportional to the logarithm of the number of entries - so if you have 256 times as many entries, it only takes 8 times the time (because log2(256)=8). Hint: Binary search is your friend...

The only way to get an array search down to near-constant time is to use a hashing function, which has hits own limitations - in particular, if your hashing function depends on the variable FOO, it becomes very fast to find the entry that corresponds to FOO - but any *other* access (such as "find entries with a value greater tha 100, for instance) is still slow....

Answer 3

I guess your question is either wrong or incorrectly worded. Searching in an array does NOT take constant time. If the array is not sorted, it takes time proportional to the length of the array. But, for a sorted array, if you use an algorithm like binary search, the time is proportional to log(length).