Question

Do not copy from other answers please! Thank you!

If you have to solve the searching problem for a list of n numbers, how can you take advantage of the fact that the list is known to be sorted? Give separate answers for

a. lists represented as arrays.

b. lists represented as linked lists.

Answer 1

a. Lists represented as arrays

Then binary search is used because the list ia know to be stored. Therefore the time complexity is required O(logn) if there are n elements in array.

In binary search first we compare the element to mid element of mid array. If found then return if mid element is greater than search is perform form 0 index to mid-1 index otherwise mid+1 to last.

b. List represented as linked list

Sequential search is performed. So here time complexity is O(n)