Question

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)?

Short answer

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.

b.) Linear: $O\left(n\right)$

Binary:$O\left({\log }_n\right)$

c.) No

Step-by-step solution

a.) Describe the linear search and binary search algorithm for finding an integer in a list of integers in increasing order.

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.) Compare the worst-case time complexities of these two algorithms.

b.) Linear searchin 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 $O\left(n\right)$

Binary searchalways 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 $2^x\ge n$ and thus $x=\left[{\log }_{2}n\right]$ . 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$⌈{\log }_{2}n⌉+1$ comparisons, while$⌈{\log }_{2}n⌉+1$ is $O\left({\log }_n\right)$

c.) Is one of these algorithms always faster than the older (measured in terms of comparisons)?

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.