10.1.2. Worst-Case Scenario

Let us look at the problem of searching for a value in an array. 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.

This chunk introduces the basic concept of searching for a specific value (K) within an array (A). It establishes that this array contains integers that can be compared to one another. The essence of searching here is to determine whether K exists within A or not.

Imagine searching for a specific book in a library; you need to find out if that book is in the collection (array). Each book’s position is like an integer, where some are 'less than' and others 'greater than' the book you're looking for.

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 may be. A systematic way to do it is to start with the position 0 and just scan all the way to n minus 1.

When the array is unsorted, we have to examine every element from the start (position 0) to the end (position n-1) to find K. This is called a linear search because you potentially have to look through every item, resulting in a time complexity of O(n).

Consider looking for a lost item in a messy room. If everything is disorganized, you need to check each corner one by one until you find what you're looking for.

The worst case actually happens when K is not an element of A. We have to scan A0 to An−1 in order to determine the case not that. This means that in the worst case, searching for an element in a non-sorted array takes linear time.

The worst-case scenario occurs when the value K does not exist in the array. To confirm this, you have to check every position in the array, leading to linear time complexity (O(n)). This is crucial when evaluating the efficiency of different searching methods.

This is akin to searching for a particular index in a phone book. If you start at the first name and go through every name until you confirm that the name is not there, you end up examining the entire book.

If the sequence is sorted, and in particular if it is an array, we can be a little more intelligent. If we probe the value in the middle and check if it is equal to K, we can decide which half of the array to search next.

For sorted arrays, we can use a more efficient searching method known as binary search. By examining the middle element and comparing it with K, we can discard half of the array from further searches. This reduces the number of comparisons needed and leads to logarithmic time complexity (O(log n)).

Think of searching for a word in a dictionary. Instead of looking page by page, you can open it in the middle to see whether the word you’re looking for is before or after. This halves the number of pages you need to check with each guess.

So, here is a simple recursive algorithm for binary search that takes a value K to search an array and two endpoints, left and right. We compute the midpoint and check for the value K. Based on the comparison, we adjust our search range accordingly.

The binary search algorithm operates recursively, refining the search to either the left half or right half of the array after checking the midpoint. This continuous halving of the search area is what makes binary search so fast and efficient compared to linear search.

Imagine playing ‘20 questions’. Each question helps narrow down the option to either a smaller group or a specific choice, eventually leading you to the answer much faster than asking every possible question.

The complexity of binary search is order of log n. We compromise a linear search in the case of an unsorted array to a logarithmic search in the case of a sorted array.

The efficiency of binary search shines through in its logarithmic time complexity. This means as the array size doubles, the number of additional steps needed grows in proportion to just one more step, which is a significant improvement over linear search's direct proportional growth.

This can be compared to using a map when driving. If you know your destination is on a road that divides several neighborhoods, taking the main road is quicker than exploring every street in those neighborhoods.

Binary search works only for arrays. This is because you need to find the midpoint in constant time. If it takes time to find the midpoint, then searching will revert to linear time.

A key limitation of binary search is that it requires random access capability found in arrays. If it has to traverse through a linked list to find the midpoint, the time complexity would revert to linear, negating the efficiency benefits of binary search.

Think of a race track with direct pathways allowing cars to quickly reach any point versus a winding road that requires driving through several other paths to get to the desired point; the former represents an array, while the latter reflects a linked list.

By only looking at a very small fraction of a sequence, we can conclude that an element is not present. Binary search demonstrates this remarkable procedure of confirming absence efficiently.

The ability of binary search to conclude whether an element exists in a large dataset by examining only a few values proves its immense efficiency. This is especially beneficial as data sizes continue to grow.

In a vast ocean of 10,000 fish, catching just a couple of them can sometimes indicate the species present without having to catch every single one to know they exist.

--