Searching Technique
__________IMPLEMENTATION WITH PYTHON
Introduction
According to time the amount of data and information stored and accessed via computer has turned to
huge databases.
So many techniques and algorithms have been developed to efficiently maintain and process information in
databases.
The processes of looking up a particular data record in the database is called searching.
Searching Algorithms are designed to check for an element or retrieve an element from any data structure where
it is used.
In a simple word searching is nothing but finding an object from a group of objects.
Introduction (contd..)
Searching is the process of finding a particular item within a collection of items.
A search typically answers whether the item is present in the collection or not.
Searching requires a key field such as name, ID, code which is related to the target item.
When the key field of a target item is found, a link to the target item is returned.
That link may be an address, an index into an array, or some other indication of where to find the target.
If a matching key field isn’t found, the user is informed.
Types of Searching Algorithm
• Linear Search Algorithm :
• Searching is done element wise from first to last in a simple sequential manner within a list or an
array.
• Binary Search Algorithm :
• Searching is done on an sorted list / array. Dividing the whole list into equal halves and elements are
searched accordingly.
Linear Search Algorithm
Linear Search Algorithm is the simplest search algorithm.
In this search algorithm a sequential search is made over all the items one by one to search for the
targeted item.
Each item is checked in sequence until the match is found.
If the match is found, particular item is returned otherwise the search continues till the end.
Linear Search starts at the beginning of the list or array.
It traversed the list or array sequentially and checks for every element of the list or array
Have a look with Linear Search !!
Linear_Search ( Array A, Value x)
Find the number 33 from the array / list
Step 1: Set i to 1
Step 2: if i > length(Array) then go to step 7
Step 3: if A[i] = x then go to step 6
Step 4: Set i to i + 1
Step 5: Go to Step 2
Step 6: Print Element x Found at index i and go
to step 8
Step 7: Print element not found
Step 8: Exit
Linear Search with Python
def linear_search(list1,key):
for i in range(len(list1)):
if key==list1[i]:
print(key,"is found at position",i)
break
else:
print("element is not found")
list1=[34,23,5,6,7,1,23,8]
print("The List is=",list1)
key=int(input("Enter the element to be searched= "))
linear_search(list1,key)
Binary Search Algorithm
Binary Search Algorithm is fast according to run time complexity.
This algorithm works on the basis of divide and conquer rule.
In this algorithm we have to sort the data collection in ascending order first.
Then search for the targeted item by comparing the middle most item of the collection.
If match found, the index of item is returned.
If the middle item is greater than the targeted item, the item is searched in the sub-array to the left of the middle item.
Otherwise, the item is searched for in the sub-array to the right of the middle item.
This process continues on the sub-array as well until the size of the sub array reduces to zero.
Have a look with Binary Search !!
Step 1: Data list must be ordered list in ascending
order. Find the number 47 from the array / list
Step 2: Identify the middle of list
Step 3: If target equals to list[mid], FOUND item.
Step 4: If target > list[mid], discard 1/2 of list between
list[mid] and list[last].
Step 5: If target < list[mid], discard 1/2 of list between
list[first] and list[mid].
Step 6: Continue searching the shortened list until
either the target is found, or there are no elements to
probe.
Binary Search with Python
def BinarySearch(list1,key):
low=0
high=len(list1)-1
Found=False
while low<=high and not Found
mid=(low+high)//2
if key==list1[mid]:
Found=True
elif key>list1[mid]:
low=mid+1
else:
high=mid-1
if Found==True:
print("Key is Found")
else:
print("Key is not Found")
list1=[23,1,4,2,3]
list1.sort()
print(list1)
key=int(input("Enter the key"))
BinarySearch(list1,key)
Sorting Technique
____________IMPLEMENTATION WITH PYTHON
Introduction
Sorting refers to the operation or technique of arranging and rearranging sets of data in some
specific order.
Sorting is the operation performed to arrange the records of a table or list in some order
according to some specific ordering criterion.
Sorting is performed according to some value of each record.
The importance of sorting lies in the fact that data searching can be optimized to a very high
level, if data is stored in a sorted manner.
Following are some of the examples of sorting in real-life scenarios −
Telephone Directory − The telephone directory stores the telephone numbers of people sorted by their names, so that
the names can be searched easily.
Dictionary − The dictionary stores words in an alphabetical order so that searching of any word becomes easy.
Introduction (contd..)
Sorting is simple concept which is the process of placing elements from a collection in some
kind of order.
For example, a list of words could be sorted alphabetically or by length.
Types of Sorting Algorithm
• According to various techniques of sorting algorithm there are many types of
sorting algorithm exists.
• But most three commonly used sorting techniques are:
1. Bubble Sort
2. Merge Sort
3. Insertion Sort
Bubble Sort Algorithm
Bubble sort, also referred to as comparison sort.
It is a simple sorting algorithm that repeatedly goes through the list.
It compares adjacent elements and swaps them if they are in the wrong order.
It is very much necessary to learn about it as it represents the basic foundations of sorting.
Now try to visualize the Bubble Sort algorithm process
Bubble Sort with Python
def bubbleSort(ar):
n = len(ar)
# Traverse through all array elements
for i in range(n):
for j in range(0, n-i-1):
# Swap if the element found is greater than the next element
if ar[j] > ar[j+1] :
ar[j], ar[j+1] = ar[j+1], ar[j]
ar = ['t','u','t','o','r','i','a','l']
bubbleSort(ar)
print ("Sorted array is:")
for i in range(len(ar)):
print (ar[i])
Merge Sort Algorithm
• Merge sort is one of the most efficient sorting algorithms.
• It works on the principle of Divide and Conquer.
• Merge sort repeatedly breaks down a list into several sub lists until each sub list consists of a single element and
merging those sub lists in a manner that results into a sorted list.
Merge Sort with Python
def mergeSort(nlist):
print("Splitting ",nlist)
if len(nlist)>1:
mid = len(nlist)//2
lefthalf = nlist[:mid]
righthalf = nlist[mid:]
mergeSort(lefthalf)
mergeSort(righthalf)
i=j=k=0
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] < righthalf[j]:
nlist[k]=lefthalf[i]
i=i+1
else:
nlist[k]=righthalf[j]
j=j+1
k=k+1
while i < len(lefthalf):
nlist[k]=lefthalf[i]
i=i+1
k=k+1
while j < len(righthalf):
nlist[k]=righthalf[j]
j=j+1
k=k+1
print("Merging ",nlist)
nlist = [14,46,43,27,57,41,45,21,70]
mergeSort(nlist)
print(nlist)
Insertion Sort Algorithm
Insertion sort is the sorting mechanism where the Have a look with the Insertion Sort mechanism !!
sorted array is built having one item at a time.
The array elements are compared with each other
sequentially and then arranged simultaneously in
some particular order.
The first step involves the comparison of the element
in question with its adjacent element.
It start with first element and compare it with next
element, to check if any swapping is needed or not.
Then proceed on next element and compare with
previous two elements and so on.
The above procedure is repeated until all the element
in the array is at their right position.
Insertion Sort with Python
def insertionSort(arr):
for i in range(1, len(arr)):
key = arr[i]
# Move elements of arr[0..i-1], that are greater than key,
# to one position ahead of their current position
j = i-1
while j >=0 and key < arr[j] :
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
arr = ['t','u','t','o','r','i','a','l']
insertionSort(arr)
print ("The sorted array is:")
for i in range(len(arr)):
print (arr[i])
