4.1: Activity 1 - Searching Algorithm

Introduction

This activity involves studying the searching process and how to write algorithms that can find a particular given item from a list of given items. The activity of searching will dedicate itself to providing the answer of a presence or no presence of the searched item. The section will dedicate itself to introducing the sequential and binary types of search.

Searching algorithm

In computer science, a search algorithm is an algorithm for finding an item with specified properties among a collection of items.

Finding a Data Item - The Search Problem

Consider a collection of data items of same type e.g. integers, and imagine we wish to check if a particular data item is in the collection. Call the particular data item of interest to us, the key. The task is then to search among the records in the database to find out which one “matches’’ the key. This can first be done by arranging the data using a structure that can hold a collection of data items of the same type, that is, the arrays or linked lists. The searching can be done using either the sequential or binary search, where the former involves looking at each item in turn while the later involves items that are in order. The example below, is of an array consisting of seven elements long, containing numeric values. That is, the maximum number of comparisons is 7, and occurs when the key we are searching for is in A[6].

Figure \(\PageIndex{1}\): an array of numbers

Both sequential and binary search algorithms can be used to find the data item:

1. For a sequential search the following will do:

   for (each item in list) {
   compare search item to current item
   if match,
   save index of matching item
   break
   }
   return index of matching item, or -1 if item not found
   

2. For a binary search, the following algorithm illustrates how it is carried out:

   set first = 1, last = N, mid = N /2
   while (item not found and first < last) {
   compare search term to item at mid
   if match
   save index
   break
   else if search term is less than item at mid,
   set last = mid-1
   else
   set first = mid+1
   set mid = (first+last) /2
   }
   return index of matching item, or -1 if not found
   

Conclusion

In this activity, you learned two different search algorithms, the sequential and binary searches. Examples illustrating them were also given. Its application to an array was also introduced i.e. how a search can be applied in an array to search for a particular item in an array.

Assessment

Provide a short description of binary search algorithm.