Scribd
Upload
10 views5 pages

Week 8 Python

The document covers the concept of recursion, explaining how recursive functions call themselves to solve problems by breaking them into smaller subproblems. It includes a practical example of checking for the presence of '0' in a list using recursion, and introduces binary search as an efficient algorithm for finding elements in a sorted array. The document also highlights the efficiency of binary search compared to obvious search methods, emphasizing its reduced time complexity.

Uploaded by

abdulganisuhaib
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
10 views5 pages

Week 8 Python

The document covers the concept of recursion, explaining how recursive functions call themselves to solve problems by breaking them into smaller subproblems. It includes a practical example of checking for the presence of '0' in a list using recursion, and introduces binary search as an efficient algorithm for finding elements in a sorted array. The document also highlights the efficiency of binary search compared to obvious search methods, emphasizing its reduced time complexity.

Uploaded by

abdulganisuhaib
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Week 8

Lecture 8.1

What is recursion?
A recursive function is one which calls itself inside the body of the function.

A recursive function solves a particular problem by calling a copy of itself and solving
smaller subproblems of the original problems.

Lecture 8.2

Recursion : A simple question

Ques :
There’s a list L,

L=[11,12,13,0,1,2,3]
We have to write a code of a recursive function which will return false if 0 is not present in the
list and return true if it is present.

The pseudocode for this is :-


Lecture 8.3

Recursion: Find 0 in a list

This is a piece of code that checks if the given list has a 0 in it or not, if yes we return
true(1), otherwise we return false(0) :-

This is not the efficient code, we'll dwell upon it later on!!

Lecture 8.4

Sorting Recursively

Code :
Lecture 8.5

Introduction to Binary Search

Binary Search is a searching algorithm for finding an element's position in a sorted array. In this
approach, the element is always searched in the middle of a portion of an array. Binary search
can be implemented only on a sorted list of items. If the elements are not sorted already, we
need to sort them first.

Algorithm is used in a sorted array by repeatedly dividing the search interval in half. The idea of
binary search is to use the information that the array is sorted and reduce the time complexity to
0.

Searching for a word in a dictionary is binary search.

Lecture 8.6

Warm up for Binary Search

Check if a given element is present in a given list L or not :

How much time does it take to find an element using obvious sort?
Finding middle most element in the list :

Lecture 8.7

Binary Search Implementation :

Checking if a given element is present in a given list L or not using binary search :

This function is an alternative to the obvious search. It is more efficient for searching, it
works on only sorted lists.
Why is searching using binary search more efficient than obvious sort?

Obvious search took nearly 2 seconds to search whereas searching was done in zero
seconds using binary search.

In obvious search, it goes through the entire list.


In binary search, it uses the principle of halving the list.

Lecture 8.8

Binary Search the Recursion Way

Code of binary search using recursion :

You might also like