Programming Exercise 2. In Python, the use the binary search functions given(rec

Question

Programming Exercise 2. In Python, the use the binary search functions given(recursive and iterative). Generate a random ordered list of integers and do a benchmark analysis. What are your results ? Explain the results.

Recursive:

def binarySearch(alist, item):
if len(alist) == 0:
return False
else:
midpoint = len(alist)//2
if alist[midpoint]==item:
return True
else:
if item<alist[midpoint]:
return binarySearch(alist[:midpoint],item)
else:
return binarySearch(alist[midpoint+1:],item)

iterative:

def binarySearch(alist, item):
first = 0
last = len(alist)-1
found = False

while first<=last and not found:
midpoint = (first + last)//2
if alist[midpoint] == item:
found = True
else:
if item < alist[midpoint]:
last = midpoint-1
else:
first = midpoint+1

return found

Explanation / Answer

very last comparison, the n``th`` comparison.

The Sequential Search ~~~~~~~~~~~~~~~~~~~~~ When data items are stored in a collection such as a list, we say that they have a linear or sequential relationship. Each data item is stored in a position relative to the others. In Python lists, these relative positions are the index values of the individual items. Since these index values are ordered, it is possible for us to visit them in sequence. This process gives rise to our first searching technique, the **sequential search**. Figure {seqsearch} shows how this search works. Starting at the first item in the list, we simply move from item to item, following the underlying sequential ordering until we either find what we are looking for or run out of items. If we run out of items, we have discovered that the item we were searching for was not present. |image| {Sequential Search of a List of Integers} {seqsearch} The Python implementation for this algorithm is shown in Listing {seqsearchpython}. The function needs the list and the item we are looking for and returns a boolean value as to whether it is present. The boolean variable ``found`` is initialized to ``False`` and is assigned the value ``True`` if we discover the item in the list. :: [caption={Sequential Search of an Unordered List},label=seqsearchpython,index={sequentialSearch},float=htb] def sequentialSearch(alist, item): pos = 0 found = False while pos < len(alist) and not found: if alist[pos] == item: found = True else: pos = pos+1 return found Analysis of Sequential Search ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ To analyze searching algorithms, we need to decide on a basic unit of computation. Recall that this is typically the common step that must be repeated in order to solve the problem. For searching, it makes sense to count the number of comparisons performed. Each comparison may or may not discover the item we are looking for. In addition, we make another assumption here. The list of items is not ordered in any way. The items have been placed randomly into the list. In other words, the probability that the item we are looking for is in any particular position is exactly the same for each position of the list. If the item is not in the list, the only way to know it is to compare it against every item present. If there are :math:`n` items, then the sequential search requires :math:`n` comparisons to discover that the item is not there. In the case where the item is in the list, the analysis is not so straightforward. There are actually three different scenarios that can occur. In the best case we will find the item in the first place we look, at the beginning of the list. We will need only one comparison. In the worst case, we will not discover the item until the

very last comparison, the n``th`` comparison.

caption={Sequential Search of an Ordered List},label=seqsearchpython2,index={orderedSequentialSearch},float=htb] def orderedSequentialSearch(alist, item): pos = 0 found = False stop = False while pos < len(alist) and not found and not stop: if alist[pos] == item: found = True else: if alist[pos] > item: stop = True else: pos = pos+1 return found caption={Binary Search of an Ordered List},label=binarysearchpy,index={binarySearch},float=htb] def binarySearch(alist, item): first = 0 last = len(alist)-1 found = False while first<=last and not found: midpoint = (first + last)//2 if alist[midpoint] == item: found = True else: if item < alist[midpoint]: last = midpoint-1 else: first = midpoint+1 return found

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.