I-Could the Sequential Search be improved (or made more efficient) if the list w
ID: 3666728 • Letter: I
Question
I-Could the Sequential Search be improved (or made more efficient) if the list was presented in some kind of ordered sequence (i.e., alphabetized or numerically ordered)? Can you think of a way to improve the efficiency of the sequential search when searching for an item that is not actually in the ordered list.
II-Explain why the binary search algorithm is so much more efficient than the sequential search algorithm. Even when you modify the sequential search to take advantage of an alphabetized (ordered) list, binary search is still more efficient. Please explain why.
Explanation / Answer
2)
>A linear search looks down a list, one item at a time, without jumping. In complexity terms this is an O(n) search the time taken to search the list gets bigger at the same rate as the list does.
A linear search would ask:
list[0] == 'U'? No.
list[1] == 'U'? No.
list[2] == 'U'? No.
list[3] == 'U'? No.
so on.........
list[20] == 'U'? Yes. Finished.
where in case with the bianry search
>A binary search is when you start with the middle of a sorted list, and see whether that's greater than or less than the value you are looking for, which determines whether the value is in the first or second half of the list. Jump to the half way through the sublist, and compare again etc. This is pretty much how humans typically look up a word in a dictionary (although we use better heuristics, obviously - if you're looking for "cat" you don't start off at "M"). In complexity terms this is an O(log n) search - the number of search operations grows more slowly than the list does, because you're halving the "search space" with each operation.
Example
>suppose you were looking for U in an A-Z list of letters
index 0-25; we're looking for the value at index 20.
The binary search would ask:
Compare list[12] ('M') with 'U': Smaller, look further on. (Range=13-25)
Compare list[19] ('T') with 'U': Smaller, look further on. (Range=20-25)
Compare list[22] ('W') with 'U': Bigger, look earlier. (Range=20-21)
Compare list[20] ('U') with 'U': Found it! Finished.
Overview:
1)Binary search requires the input data to be sorted
linear search doesn't requires the input data to be sorted
2)Binary search requires an ordering comparison
linear search only requires equality comparisons
3)Binary search has complexity O(log n)
linear search has complexity O(n) as discussed earlier
4)Binary search requires random access to the data
linear search only requires sequential access