For sequential search, what is the average number of comparisons needed to find a record in a file?
+3
A:
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.
Mark Byers
2010-03-06 17:24:27
And a worst case of all the records when the value is not in the file.
Jonathan Leffler
2010-03-06 17:25:47
I have also seen it as (n+1)/2. Why n+1?
Phenom
2010-03-06 18:23:41
@Phenom: It's because you can start with two different assumptions. If you assume that you know that the entry is in the file and you just need to find the index, the minimum number of comparisions is 1 and the maximum is (n-1), with an average of ((n-1)+1)/2 = n/2. If you assume you don't know that the entry is in the file the minimum is 1, the maximum is n, and so the average is (n+1)/2 in the case that the element was in the file, and n if it is not.
Mark Byers
2010-03-06 18:39:35
+1
A:
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)
Leniel Macaferi
2010-03-06 17:30:11