10.1. Searching in an array

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, which we will think of as a sequence of values. Moreover, we also assume that the sequence consists of integers, which can be ordered with respect to each other.

This chunk introduces the concept of searching within an array, emphasizing that the objective is to find a value, referred to as K, within a collection called A. This collection is specifically an ordered sequence of integers, meaning that each integer can be compared in terms of their sizes (e.g., one integer can be less than or greater than another).

Imagine searching for a specific book in a library. The books on the shelves are arranged in a certain order (like integers in an array), making it easier to find the book you’re looking for by systematically checking titles in that order.

We can keep sequences of values in two different ways: as arrays and as lists. Depending on the data structure chosen, the method of accessing elements varies. We should consider if searching is different based on whether the collection is a list or an array.

In this chunk, the differentiation between arrays and lists is highlighted. Each data structure has unique methods for accessing its elements, which can impact how efficiently we can search for a value. This sets the stage for understanding why the choice of data structure matters when implementing search algorithms.

Think about how you might look for a highlighted passage in a printed book (like an array) versus a digital document (like a list). In a printed book, you typically flip through pages, while in a digital document, you might use a search function that shows results instantly.

In the unsorted case, we have no choice but to scan all the values in the sequence A. This entails starting from position 0 and scanning to n minus 1. The search terminates either upon finding K or reaching the end without finding it, resulting in an output of -1 if not found.

This chunk explains how searching works in an unsorted array. Since the values are not arranged in any specific order, the only approach is to check each element sequentially. This method is straightforward but time-consuming, especially for larger arrays.

Consider searching for a specific ingredient in a messy kitchen. You would have to inspect each corner (each element of the array) one by one until you find what you need or determine that it isn’t there.

The worst-case scenario occurs when K is not an element of A, requiring a scan of all elements from A0 to An−1, leading to a linear time complexity for searching in an unsorted array.

This chunk highlights that the worst-case time complexity of searching in an unsorted array is linear, which means that for n elements, you might have to examine practically all of them. This inefficiency is essential to recognize when choosing a search strategy.

If you’re looking for a specific item in a large, unorganized storage room, the worst-case scenario is that the item is either lost or buried at the very end, forcing you to look through every box (every element) without any shortcut.

If the sequence is sorted, we can utilize a more efficient method called binary search. By probing the value in the middle of the array, we can significantly reduce our search interval, depending on whether K is less than or greater than the midpoint.

This chunk introduces binary search, a much more efficient algorithm used for searching in sorted arrays. By repeatedly dividing the search interval in half (by comparing K with the midpoint), binary search drastically reduces the number of comparisons needed to find the element or determine its absence.

Think of how you might locate a word in a dictionary. You start in the middle and based on whether the word comes earlier or later in the alphabet, you narrow your search down to specific sections, greatly speeding up your search compared to checking each entry one by one.

The binary search algorithm uses recursion to search through an array. It takes a value K, along with two endpoints, left (l) and right (r), searching from index l to r but excluding r. If the interval becomes empty, the search ceases with a negative indication. Midpoints are calculated to guide subsequent searches.

This chunk describes how binary search is structured as a recursive algorithm, outlining how to define boundaries and compute the midpoint. If the value found at the midpoint isn’t K, the algorithm chooses to search either the left or right half of the current interval, excluding the midpoint in the process.

Imagine a game of 20 Questions where you drill down on the attributes of something you’re thinking of. Depending on the answer, you either focus on a narrower set of possible items, effectively ruling out options based on a midpoint guess each time.

Binary search leads to a recurrence relation for time complexity, typically expressed as T(n) = 1 + T(n/2). After a number of steps, the search eventually narrows down to a single element, giving it a logarithmic time complexity of O(log n).

In this chunk, we analyze how the recursive nature of binary search affects its performance in terms of time complexity. Each step reduces the search space by half, leading to an efficient algorithm with a logarithmic relationship to the size of the input array.

Returning to the dictionary analogy, the number of pages you need to look through decreases exponentially as you gain more information. Instead of checking every word, you quickly eliminate half the pages with each question.

Binary search works optimally in sorted arrays. If required to find midpoints in data structures where accessing them isn’t constant time, performance can degrade to linear time, as seen in some list implementations.

This chunk points out a potential limitation of binary search. While powerful in sorted arrays, if the underlying data structure (like a linked list) does not permit constant-time access to its elements, the advantages of binary search may be lost, returning us to linear time search strategies.

Picture trying to find a page in a spiral-bound notebook. If you can only flip through the pages one by one (like accessing elements in a linked list), even though they are in order, it would take you significantly longer than quickly jumping to any page as you would in a traditional book (like an array).

--