sequential search

For sequential search, what is the average number of comparisons needed to find a reco开发者_JS百科rd in a file?

A sequential search starts from the beginning of the file and checks each element one-by-one until the desired element is found. Assuming that the record you are searching for exists in the file exactly once and could be anywhere in the file with equal probability, the average number of comparisons is equal to half the number of records in the file.

However if the record does not exist in the file, you will have to examine every single record in the file before discovering this.

For a list with n items, the best case is when the value is equal to the first element of the list, in which case only one comparison is needed. The worst case is when the value is not in the list (or occurs only once at the end of the list), in which case n comparisons are needed.

Asymptotically, therefore, the worst-case cost and the expected cost of linear search are both O(n)

I would like to add few points that the previous answers fails to point out:

• On the other hand, we must consider whether the file is available on one device or spread over multiple devices. In case of T rams, then the complexity will be O(T*N/(1+log(T))).

• In general, sequential search takes O(N) time complexity.

• When combined with data structures such as R-Tree, it can give a best case time complexity of O(N/(log(log(N)))) in the case of records in a file.

• It depends on the structure/ format of the file such that if the data fields are available in a hash map, sequential search is a backlog.