Linear Search and Binary search
Aim:
To write a program to perform linear search and binary search using python programming.
Equipment’s required:
- Hardware – PCs
- Anaconda – Python 3.7 Installation / Moodle-Code Runner
Algorithm:
Linear Search:
- Start from the leftmost element of array[] and compare k with each element of array[] one by one.
- If k matches with an element in array[] , return the index.
- If k doesn’t match with any of elements in array[], return -1 or element not found.
Binary Search:
- Set two pointers low and high at the lowest and the highest positions respectively.
- Find the middle element mid of the array ie. arr[(low + high)/2]
- If x == mid, then return mid.Else, compare the element to be searched with m.
- If x > mid, compare x with the middle element of the elements on the right side of mid. This is done by setting low to low = mid + 1.
- Else, compare x with the middle element of the elements on the left side of mid. This is done by setting high to high = mid - 1.
- Repeat steps 2 to 5 until low meets high
Program:
i) #Use a linear search method to match the item in a list.
'''
Program for linear search method to match the item in a list
Developed by: your name: Jegathish s
RegisterNumber: 21005410
'''
def linearSearch(array,n,k):
for i in range(0,n):
if array[i]==k:
return i
return -1
array = eval(input())
# sort the array
array.sort()
print(array)
# k-item to be seared for
k = eval(input())
# get the length of array and store in the variable n
n=len(array)
# use the function for linear search
result=linearSearch(array,n,k)
# use if-else to print sorted array and "Element not found" if the item is not present in the list otherwise print sorted array and "Element found at index: ", result
if result>=0:
print("Element found at index: ",result)
else:
print("Element not found")
ii) # Find the element in a list using Binary Search(Iterative Method).
'''
Program to find the element in a list using Binary Search(Iterative Method)..
Developed by: your name: Jegathish s
RegisterNumber: 21005410
'''
def binarySearchIter(array, k, low, high):
# Write your code here to find the middle value and check if the desired item is above or below the middle value
while(low<=high):
mid=low+(high-low)//2
if array[mid]==k:
return mid
elif array[mid]<k:
low=mid+1
else:
high=mid+1
return -1
array = eval(input())
#sort the array
array.sort()
print(array)
#k-item to be searched
k = eval(input())
low=0
high=len(array)-1
# use the binary search function to find the item in the list
result=binarySearchIter(array, k, low, high)
# use if-else to print sorted array and "Element not found" if the item is not present in the list otherwise print sorted array and "Element found at index: ", result
if result>=0:
print("Element found at index: ",result)
else:
print("Element not found")
iii) # Find the element in a list using Binary Search (recursive Method).
'''
Program for linear search method to match the item in a list
Developed by: your name: Jegathish s
RegisterNumber: 21005410
'''
def linearSearch(array,n,k):
for i in range(0,n):
if array[i]==k:
return i
return -1
array = eval(input())
# sort the array
array.sort()
print(array)
# k-item to be seared for
k = eval(input())
# get the length of array and store in the variable n
n=len(array)
# use the function for linear search
result=linearSearch(array,n,k)
# use if-else to print sorted array and "Element not found" if the item is not present in the list otherwise print sorted array and "Element found at index: ", result
if result>=0:
print("Element found at index: ",result)
else:
print("Element not found")
Sample Input:
Output 1:
Output 2:
Output 3:
Result
Thus the linear search and binary search algorithm is implemented using python programming.