Consider a finite collection of element. Finding whether element exsists in collection is known as Searching. Following are some of the comparision based Searching Algorithms.
Before looking at the analysis part, we shall examine the Language in built methods to searching
in
operator and list.index()
We have already seen the in
operator in several contexts. Let's see the working of in
operator again
In [1]:
x = list(range(10))
In [2]:
x
Out[2]:
In [3]:
6 in x
Out[3]:
In [4]:
100 in x
Out[4]:
In [5]:
x.index(6)
Out[5]:
In [6]:
x.index(100)
In [16]:
from openanalysis.searching import SearchingAlgorithm,SearchAnalyzer
%matplotlib inline
%config InlineBackend.figure_formats={"svg", "pdf"}
SearchingAlgorithm
is the base class providing the standards to implement searching algorithms, SearchAnalyzer
analyses the algorithm
SearchingAlgorithm
classAny searching algorithm, which has to be implemented, has to be derived from this class. Now we shall see data members and member functions of this class.
name
- Name of the Searching Algorithmcount
- Holds the number of basic operations performed__init__(self, name):
- Initializes algorithm with a name
search(self, array, key):
_ The base searching function. Sets count
to 0. array
is 1D numpy
array,key
is the key of element to be found outNow we shall implement the class BinarySearch
In [17]:
class BinarySearch(SearchingAlgorithm): # Inheriting
def __init__(self):
SearchingAlgorithm.__init__(self, "Binary Search") # Initailizing with name
def search(self, arr, key):
SearchingAlgorithm.search(self, arr, key) # call base class search
low, high = 0, arr.size - 1
while low <= high:
mid = int((low + high) / 2)
self.count += 1 # Increment for each basic operation performed
if arr[mid] == key:
return True
elif arr[mid] < key:
low = mid + 1
else:
high = mid - 1
return False
SearchAnalyzer
classThis class provides the visualization and analysis methods. Let's see its methods in detail
__init__(self, searcher):
Initializes visualizer with a Searching Algorithm. searcher
is a class, which is derived from SearchingAlgorithm
analyze(self, maxpts=1000):
maxpts
in the steps of 100, and counting the number of
basic operationsmaxpts
Upper bound on size of elements chosen for analysing efficiency
In [18]:
bin_visualizer = SearchAnalyzer(BinarySearch)
In [19]:
bin_visualizer.analyze(progress=False)
Note $\mathcal{O}(\log{}n)$ performance in all cases
You can see more examples at Github