A binary search of 1,000 elements would be, on average, 50× faster than a sequential search. A sequential search checks each element of an array list until a matching element is found. The process can be represented with the equation S(n) = n ∕ 2, where n represents the number of elements in the array list and S(n) represents the average number of sequential comparisons it will take. Thus, an array of 1,000 elements would take, on average, 500 comparisons to target. A binary search sorts the array list in ascending order, then checks the median value of the list. If the value of the element being searched for is less than the median, then the procedure is repeated with the left half of the array; else, the procedure is repeated with the right half of the array. This process can be represented with the equation B(n) = log₂(n), where n represents the number of elements in the array list and B(n) represents the average number of binary comparisons it will take. Thus, an array of 1,000 elements would take, on average, about 10 comparisons to target. Therefore, a binary search of 1,000 elements would be, on average, 50× faster than a sequential search.
−Phoenix
No comments:
Post a Comment