Loading...
More Python Posts
""" Binary Search Algorithm----------------------------------------"""#iterative implementation of binary search in Pythondef binary_search(a_list, item):"""Performs iterative binary search to find the position of an integer in a given, sorted, list.a_list -- sorted list of integersitem -- integer you are searching for the position of"""first = 0last = len(a_list) - 1while first <= last:i = (first + last) / 2if a_list[i] == item:return ' found at position '.format(item=item, i=i)elif a_list[i] > item:last = i - 1elif a_list[i] < item:first = i + 1else:return ' not found in the list'.format(item=item)#recursive implementation of binary search in Pythondef binary_search_recursive(a_list, item):"""Performs recursive binary search of an integer in a given, sorted, list.a_list -- sorted list of integersitem -- integer you are searching for the position of"""first = 0last = len(a_list) - 1if len(a_list) == 0:return ' was not found in the list'.format(item=item)else:i = (first + last) // 2if item == a_list[i]:return ' found'.format(item=item)else:if a_list[i] < item:return binary_search_recursive(a_list[i+1:], item)else:return binary_search_recursive(a_list[:i], item)
# Python program to reverse a linked list# Time Complexity : O(n)# Space Complexity : O(n) as 'next'#variable is getting created in each loop.# Node classclass Node:# Constructor to initialize the node objectdef __init__(self, data):self.data = dataself.next = Noneclass LinkedList:# Function to initialize headdef __init__(self):self.head = None# Function to reverse the linked listdef reverse(self):prev = Nonecurrent = self.headwhile(current is not None):next = current.nextcurrent.next = prevprev = currentcurrent = nextself.head = prev# Function to insert a new node at the beginningdef push(self, new_data):new_node = Node(new_data)new_node.next = self.headself.head = new_node# Utility function to print the linked LinkedListdef printList(self):temp = self.headwhile(temp):print temp.data,temp = temp.next# Driver program to test above functionsllist = LinkedList()llist.push(20)llist.push(4)llist.push(15)llist.push(85)print "Given Linked List"llist.printList()llist.reverse()print "\nReversed Linked List"llist.printList()
# Python binary search functiondef binary_search(arr, target):left = 0right = len(arr) - 1while left <= right:mid = (left + right) // 2if arr[mid] == target:return midelif arr[mid] < target:left = mid + 1else:right = mid - 1return -1# Usagearr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]target = 7result = binary_search(arr, target)if result != -1:print(f"Element is present at index {result}")else:print("Element is not present in array")
#Python program to print topological sorting of a DAGfrom collections import defaultdict#Class to represent a graphclass Graph:def __init__(self,vertices):self.graph = defaultdict(list) #dictionary containing adjacency Listself.V = vertices #No. of vertices# function to add an edge to graphdef addEdge(self,u,v):self.graph[u].append(v)# A recursive function used by topologicalSortdef topologicalSortUtil(self,v,visited,stack):# Mark the current node as visited.visited[v] = True# Recur for all the vertices adjacent to this vertexfor i in self.graph[v]:if visited[i] == False:self.topologicalSortUtil(i,visited,stack)# Push current vertex to stack which stores resultstack.insert(0,v)# The function to do Topological Sort. It uses recursive# topologicalSortUtil()def topologicalSort(self):# Mark all the vertices as not visitedvisited = [False]*self.Vstack =[]# Call the recursive helper function to store Topological# Sort starting from all vertices one by onefor i in range(self.V):if visited[i] == False:self.topologicalSortUtil(i,visited,stack)# Print contents of stackprint(stack)g= Graph(6)g.addEdge(5, 2);g.addEdge(5, 0);g.addEdge(4, 0);g.addEdge(4, 1);g.addEdge(2, 3);g.addEdge(3, 1);print("Following is a Topological Sort of the given graph")g.topologicalSort()
#84 48 13 20 61 20 33 97 34 45 6 63 71 66 24 57 92 74 6 25 51 86 48 15 64 55 77 30 56 53 37 99 9 59 57 61 30 97 50 63 59 62 39 32 34 4 96 51 8 86 10 62 16 55 81 88 71 25 27 78 79 88 92 50 16 8 67 82 67 37 84 3 33 4 78 98 39 64 98 94 24 82 45 3 53 74 96 9 10 94 13 79 15 27 56 66 32 81 77# xor a list of integers to find the lonely integerres = a[0]for i in range(1,len(a)):res = res ^ a[i]
# Python code to demonstrate# method to remove i'th character# Naive Method# Initializing Stringtest_str = "CodeCatch"# Printing original stringprint ("The original string is : " + test_str)# Removing char at pos 3# using loopnew_str = ""for i in range(len(test_str)):if i != 2:new_str = new_str + test_str[i]# Printing string after removalprint ("The string after removal of i'th character : " + new_str)