Embedded Files
Henceforth, in the context of searching and sorting problems, we will assume that the elements are drawn from a linearly ordered set, for example, the set of integers. This will also be the case for similar problems, such as finding the median, the kth smallest element, and so forth. Let A[1..n] be a sequence of n elements. Consider the problem of determining whether a given element x is in A. This problem can be rephrased as follows.
Find an index j, 1 ≤ j ≤ n, such that x = A[j] if x is in A, and j = 0 otherwise. A straightforward approach is to scan the entries in A and compare each entry with x. If after j comparisons, 1 ≤ j ≤ n, the search is successful, i.e., x = A[j], j is returned; otherwise, a value of 0 is returned indicating an unsuccessful search. This method is referred to as sequential search. It is also called linear search, as the maximum number of element comparisons grows linearly with the size of the sequence.
Note: Learners must have a background in array in order for them to understand the following topic
Linear Search Sample Algorithm
Linear search is a very simple search algorithm. In this type of search, a sequential search is made over all items one by one. Every item is checked and if a match is found then that particular item is returned, otherwise the search continues till the end of the data collection.
Intuitively, scanning all entries of A is inevitable if no more information about the ordering of the elements in A is given. If we are also given that the elements in A are sorted, say in nondecreasing order, then there is a much more efficient algorithm. The following example illustrates this efficient search method.
Example 1.1
Consider searching the array
In this instance, we want to search for element x = 22. First, we compare x with the middle element A[(1 + 14)/2] = A[7] = 10. Since 22 > A[7], and since it is known that A[i] ≤ A[i+1], 1 ≤ i < 14, x cannot be in A[1..7], and therefore this portion of the array can be discarded. So, we are left with the subarray
Next, we compare x with the middle of the remaining elements A[(8 + 14)/2] = A[11] = 23. Since 22 < A[11], and since A[i] ≤ A[i + 1], 11 ≤ i < 14, x cannot be in A[11..14], and therefore this portion of the array can also be discarded. Thus, the remaining portion of the array to be searched is now reduced to
Repeating this procedure, we discard A[8..9], which leaves only one entry in the array to be searched, that is, A[10] = 22. Finally, we find that x = A[10], and the search is successfully completed. In general, let A[low..high] be a nonempty array of elements sorted in nondecreasing order. Let A[mid] be the middle element, and suppose that x>A[mid]. We observe that if x is in A, then it must be one of the elements A[mid + 1], A[mid + 2],...,A[high]. It follows that we only need to search for x in A[mid + 1..high]. In other words, the entries in A[low..mid] are discarded in subsequent comparisons since, by assumption, A is sorted in nondecreasing order, which implies that x cannot be in this half of the array. Similarly, if x<A[mid], then we only need to search for x in A[low..mid−1]. This results in an efficient strategy which, because of its repetitive halving, is referred to as binary search.
An algorithm binary search gives a more formal description of this method.
Page updated
Report abuse