10.1.1. Unsorted Case

So, in general the search problem is to find whether a value K is present in a collection of values A and in our case we will think of A as generally a sequence of values. Moreover, we also assume that the sequence is something like integers, where we can talk of one value being less than another value. So, the values can be ordered with each other.

The search problem involves determining if a specific value (K) exists within a collection (A). In this context, A is treated as a list of numbers (integers). These integers can be compared to one another based on their value, establishing a hierarchy of less than or greater than. This sets the foundation for how we approach searching within the collection.

Imagine you're searching for a specific book in a stack of books. The books can be compared based on their titles or authors, and you can determine which book comes first or last in the stack.

So, in the unsorted case we have no choice basically; we have a sequence A which runs from 0 to n minus 1. So, we must look at all the values because we have no idea where K might be. A systematic way to do it is to start with position 0 and just scan all the way to n minus 1.

In an unsorted array, there is no predefined order of the elements, making it necessary to review each element sequentially. This means starting from the first element (index 0) and moving through to the last (index n-1) until either K is found or all elements have been examined.

Think of searching for a specific toy in a toy box. Since the toys are not organized, you have to pull each one out and check until you find the one you're looking for, or until the box is empty.

So we scan, and this scan either terminates when you reach the end without finding it or when at some position i, we find that A i is equal to K. Depending on that, we either say that it is found, in which case we return the position or we have reached i equal to n, which means we are gone beyond A n minus 1 and so, we return naught -1 which is an invalid position to indicate that it is not found.

The search process concludes when either the target value K is located (and its position is returned), or all elements in the array have been scanned without success, leading to an indication (usually -1) that K isn’t present.

When you search for a specific recipe in a cookbook, you either find the recipe and note its page number, or if you reach the end of the book without finding it, you conclude that the recipe doesn't exist in that book.

So, we saw before that the worst case actually happens when K is not an element of A; K does not come in A. We have to scan A from position 0 to A n minus 1 in order to determine that.

The worst-case scenario occurs when the value K is not found in the array A, necessitating a complete scan of all elements from the start to the end position. The time complexity for this operation is linear, referred to as O(n), where n is the number of elements in A.

Consider searching for a lost item in your house. If the item isn't there, you may need to search every room, which can take a long time, especially if you have many rooms to check.

This means that in the worst case searching for an element in a non-sorted array takes linear time. And of course, it does not matter now whether it is an array or a list because, in a list, we could also in linear time start from the first element and follow the links all the way to the end.

The time complexity for searching in either an unsorted array or a linked list is linear (O(n)). This similarity arises because both structures require examining each element, one after the other, until the desired element is found or all options are exhausted.

Imagine looking for a specific outfit in your closet. Whether your clothes are hung up in an orderly fashion or piled in bins, you’ll likely have to look at each piece of clothing sequentially until you find what you’re looking for.

--