Get ready to dive into the exciting world of Python with me! In my upcoming article, "8th Week Python Experience," we'll explore essential topics such as recursion, sorting recursively, and practical applications, all while delving into the intriguing concept of binary search. Stay tuned for a comprehensive journey through these fundamental Python concepts!
More on Recursion
def find0(l):
if len(l)!=0:
if l[0]==0:
return True
else:
return find0(l[1:len(l)])
else:
return(False)
print(find0([1,2,3,4,5,6,7,8,9,])) # O/P : False
This Python function, find0(l), is designed to search for the presence of the value 0 within a given list l. Here's a breakdown of how it works:
The function begins by checking if the length of the list
lis not equal to zero, ensuring that there are elements to search within.If the list is not empty, it examines the first element (
l[0]) of the list. If it's equal to 0, the function returnsTrue, indicating that the value 0 has been found.If the first element is not 0, the function recursively calls itself with the remainder of the list (
l[1:len(l)]), effectively reducing the size of the list by one element with each recursive call.This recursive process continues until either the value 0 is found or the list becomes empty.
If the list becomes empty and the value 0 hasn't been found, the function returns
False, indicating that the value 0 is not present in the list.
In summary, this function recursively searches through the elements of the list to determine if the value 0 exists within it, returning True if found and False otherwise.
def mini(l):
mini=l[0]
for i in l:
if i<mini:
mini=i
return mini
def sort(l):
if l==[]or len(l)==1:
return l
m=mini(l)
l.remove(min)
return ([m]+sort(l))
These two Python functions work together to perform a basic sorting algorithm:
The
mini(l)function finds the minimum value in the listlby iterating through each element and comparing it with the current minimum value. It returns the smallest element found.The
sort(l)function sorts the listlby repeatedly finding the minimum value usingmini(l)and removing it from the list until the list is empty. It then returns a sorted list.
The sort(l) function operates recursively, continuously finding the minimum value and removing it from the list until the list is empty. It then returns a sorted list.
Binary search
lets understand it by a game :
Imagine you have a huge dictionary with 1000 pages, each page containing a lot of words arranged in alphabetical order. Now, you want to find the word "serendipity" in this dictionary.
You start by opening the dictionary right in the middle, at page 500. You check the first word on that page. Let's say it's "rainbow". Now, you think: "Hmm, where would 'serendipity' be compared to 'rainbow'?" Since 'serendipity' comes after 'rainbow' in the alphabet, you know it should be on a page after page 500.
So, you flip forward to the middle of the second half of the dictionary, which is around page 750. Again, you look at the first word on that page. Let's say it's "sparkle". Now, you compare 'serendipity' with 'sparkle'. 'Serendipity' comes after 'sparkle', so you know you need to look in the pages after page 750.
You keep doing this, dividing the remaining pages in half each time and comparing the first word on the page with 'serendipity'. Eventually, you'll get to a page where the first word is 'serendipity', and you'll know you've found it!
This method of finding words in the dictionary quickly by splitting the pages in half and comparing them is just like how binary search works. It's a clever way to find things in a big list (or dictionary) without having to look at each and every item one by one. Cool, isn't it?
Before jumping in to binary search officially , lets just discuss a function of a library (time function of time library):
The time module in Python provides various functions to work with time, including measuring time intervals. One of the key functions is time().
Here's a brief explanation of the time() function and an example demonstrating its use in calculating the time taken to execute a piece of code:
time() Function:
The
time()function returns the current time in seconds since the epoch (00:00:00 UTC, January 1, 1970).It's commonly used to measure time intervals or to benchmark the performance of code.
Example Use Case:
Suppose you have a Python script with two points of interest: before executing a specific code block and after executing the same code block.
You want to measure how long it takes to execute this code block.
Here's how you can achieve this:
import time
# Record the start time
start_time = time.time()
# Your code block to be measured
# For example, let's say we're summing numbers from 1 to 1 million
total = 0
for i in range(1, 1000001):
total += i
# Record the end time
end_time = time.time()
# Calculate the time taken
elapsed_time = end_time - start_time
print(f"Time taken to execute the code: {elapsed_time} seconds")
In this example:
We import the
timemodule.We record the start time using
time.time()just before the code block we want to measure.We execute our code block (in this case, summing numbers from 1 to 1 million).
We record the end time just after the code block.
We calculate the elapsed time by subtracting the start time from the end time.
Finally, we print out the time
Now finally On Binary search:
Binary search is a fast and efficient algorithm used to find a specific target value within a sorted list or array. Here's a simple explanation of how it works:
Assumption: The list or array must be sorted beforehand for binary search to work effectively.
Divide and Conquer: Binary search follows a "divide and conquer" approach. It repeatedly divides the search interval in half until the target value is found or the interval is empty.
Comparison with Midpoint: It begins by comparing the target value with the middle element of the list.
Three Possibilities:
If the target value matches the middle element, the search is successful, and the index of the target value is returned.
If the target value is less than the middle element, the search continues in the lower half of the list.
If the target value is greater than the middle element, the search continues in the upper half of the list.
Repeat: Steps 3 and 4 are repeated until the target value is found or the search interval becomes empty.
def binary_search(L,k):
#shrink the list using while loop
begin = 0 #first element in list, L[0]
end = len(L)-1 #last element of list, L[Len(L)-1]
while(end-begin>1): #use while loop to look at the list and keep halving it.
mid=(begin+end)//2 #compute the mid which is midpoit of begin to end
if L[mid]==k: #if mid is indeed k, return 1
return 1
#if the middle element is greater than k, then cut the right side and retain the left side or vice-versa
if L[mid]>k:
end = mid-1
if L[mid]<k:
begin = mid+1
#we are outside the while loop now. This means condition in while loop is violated or the length of list is less than or equal to 1
#if it is equal to 1, that means there are exactly two elements
if L[begin]==k or L[end]==k:
return 1
else:
return 0
see the efficiency in code when the list is too big ..
Binary search and linear(Obvious) search (which I assume you're referring to as "obvious search") are two fundamentally different search algorithms with their own strengths and weaknesses:
Binary Search:
Efficiency: Binary search is highly efficient, especially for sorted arrays. It has a time complexity of O(log n), where n is the number of elements in the array.
Prerequisite: Requires the array to be sorted beforehand. If the array is not sorted, binary search cannot be used.
Search Space Reduction: It repeatedly divides the search space in half, efficiently narrowing down the possible locations of the target value.
Optimal for Large Datasets: Binary search excels when dealing with large datasets, as it drastically reduces the number of comparisons needed to find the target value.
Linear Search:
Simplicity: Linear search, also known as sequential search, is straightforward and easy to implement. It involves iterating through each element in the array until the target value is found.
No Sorting Requirement: Linear search does not require the array to be sorted. It can be applied to both sorted and unsorted arrays.
Time Complexity: Linear search has a time complexity of O(n), where n is the number of elements in the array. This means that the time taken to perform a linear search increases linearly with the size of the array.
Use Cases: Linear search is suitable for small datasets or situations where the array is not sorted and there's no need for optimization.
In summary, binary search is highly efficient but requires a sorted array, while linear search is simpler and more flexible but less efficient, especially for large datasets. The choice between the two depends on the specific requirements of the problem at hand, including the size of the dataset, whether the array is sorted, and the desired level of efficiency.
Recursive way for Binary Search :
''' a code for recursive way of doing biunary serach '''
def rbinarysearch(L,k,begin,end):
if(begin==end):
if(L[begin]==k):
return 1
else:
return 0
if(end-begin==1):
if(L[begin]==k or L[end]==k):
return 1
else:
return 0
if(end-begin>1):
mid=(begin+end)//2
if(L[mid]>k):
end=mid-1
if(L[mid]<k):
begin=mid+1
if(L[mid]==k):
return 1
if(end-begin<0):
return 0
return rbinarysearch(L,k,begin,end)
A word of caution :
Recursion, while a powerful and elegant concept in programming, can sometimes lead to issues if not used carefully. Memory Consumption: Each recursive call consumes memory by adding a new stack frame to the call stack. In cases where recursion depth is significant, it can lead to high memory consumption, potentially causing performance issues or even crashing the program.