a.) Describe the linear search and binary search algorithm for finding an integer in a list of integers in increasing order.
b.) Compare the worst-case time complexities of these two algorithms.
c.) Is one of these algorithms always faster than the other (measured in terms of comparisons)?
a.) Linear search searches for the integer by comparing the integer with the first element in the list, then with the second element, then the third and so on. If the element is found, then the algorithm stops and the position of the element is returned.
a.) Linear search searches for the integer by comparing the integer with the first element in the list, then with the second element, then the third so on. If the element is found, then the algorithm stops and the position of the element is returned.
Binary search divides the list of integers in two halves. It determines in which half the integer needs to lie (using the increasing order of the initial list) and then the half becomes the new list of the integers. We then divide the list in half again and again determine in which half of the integer lies, which then becomes the new list. This is repeated until the list contains only 1 value. If this value is the integer that we are looking for, the position is returned, else 0 is returned (indicating that the element is not in the list)
b.) Linear search in worst case, the integer is not in the list or is the last element in the list, then every element of the list needs to get searched. If the list contains n elements, then we thus make n comparisons and n is
Binary search always executes the algorithm until the list only contains 1 element. Since in every iteration, the list is divide in half, the number of iterations x is such that and thus . Finally 1 more comparison is made (to determine if the remaining element in the list is also the element that we are looking for) and thus in total there are comparisons, while is
c.) One algorithm is not always faster than the other algorithm
For example, if the list contains elements.
Binary search then requires only 3 comparisons (twice dividing in half and then check the remaining element in the list)
However, linear search requires only 1 comparison, if the element for which we are looking is the first element in the list, and linear search requires 4 comparisons, if the element for which we are looking is the last element in the list.
Thus linear search could be faster or slower than binary search.
a) Adapt Algorithm 1 in Section 3.1 to find the maximum and the minimum of a sequence of elements by employing a temporary maximum and a temporary minimum that is updated as each successive element is examined.
b) Describe the algorithm from part (a) in pseudocode.
c) How many comparisons of elements in the sequence are carried out by this algorithm? (Do not count comparisons used to determine whether the end of the sequence has been reached.)
94% of StudySmarter users get better grades.Sign up for free