Competitive Python

Binary Search Okay, so how do you think we can search for a paticular element in an array? One obvious way will be to loop through the array and return true at which the element is found and to return false if it doesn't exist in the array. But the problem with this algorithm known as linear search is that it can very quickly turn out to be very costly in terms of space and time as this algorithm takes O(n) or linear time. This turns out to be highly costly for a large number of elements in an array. #Linear Search --> def linear_search(array , n ): for i in array: if i == n : return True So, the solution to this is to use an algorithm called binary search . Binary search is an algorithm that works on the divide and conquer technique and is also extremely efficient.It works on O(logn). But the only catch to this algorithm is that the array it is being applied on needs to be sorted . #Binary Search --> def binary_search(array, n ): #Setting up search ...

Divide and Conquer Divide and Conquer is an algorithmic paradigm used in many problems and algorithms . Some of the most common algorithms use divide and conquer principle and are highly effective. A Divide and Conquer algorithm solves a problem in 3 steps : Divide: Break the given problem into subproblems of same type. Conquer: Recursively solve these subproblems Combine: Appropriately combine the answers It starts of by breaking down a problem into multiple parts that are simple enough to be solved and then all these subparts are solved individually. For the last part , the algorithm combines all the solutions into one. Some common examples of Divide and Conquer in algorithms are - Binary Search Merge Sort Quick Sort Divide and Conquer is the principle applied to recursion and thus it is a very important technique and is of immense use for programmers. Resources - Wikipedia Technical details