Course Content

Binary Search in Python

1. Binary Search

2. Problems

Sqrt(n)Arrays Intersection Mountain Peak Balloons Division

BinarySearch 1/2

Binary search follows a 'divide and conquer' approach, when the list is divided into two halves and the element is compared with the middle element of the list. If a match is found, the location of the middle element is returned. We are goimg to implement the BS with the help of the recursion!

The main steps to implement the binary search algorithm:

Compare x(the desired item) with the middle element
If x matches with the middle element, we return the mid index
Else If x is greater than the mid element, then x can only lie in the right half subarray after the mid element
Else (x is smaller) recur for the left half
If none of it, the element isn't in the array

Why Binary search?

Study the table to understand why BS is better than the Linear Search!

Binary search works only if elements of the array are arranged in sorted order.

Linear search	Binary Search
The linear search starts searching from the first element and compares each element with a searched element till the element is not found	It finds the position of the searched element by finding the middle element of the array
The worst-case scenario for finding the element is O(n)	The worst-case scenario for finding the element is O(log2n)(beter!)
It is preferrable for the small-sized data sets	It is preferrable for the large-size data sets(better!)

Now we will try to implement the BS algorithm! Use hints if needed! Be careful with the tabulation!

Task

Set condition if the right is greater than the left.
Set the middle varible. The middle equals the left + (right - left) // 2.
Set condition if the element in the middle equals the x.
Perform recursion with the left part of the array if the x is greater than the middle element.
Perform recursion with the right part of the array if the x is lower than the middle element.

Task

Set condition if the right is greater than the left.
Set the middle varible. The middle equals the left + (right - left) // 2.
Set condition if the element in the middle equals the x.
Perform recursion with the left part of the array if the x is greater than the middle element.
Perform recursion with the right part of the array if the x is lower than the middle element.

Everything was clear?

Section 1. Chapter 1

BinarySearch 1/2

The main steps to implement the binary search algorithm:

Compare x(the desired item) with the middle element
If x matches with the middle element, we return the mid index
Else If x is greater than the mid element, then x can only lie in the right half subarray after the mid element
Else (x is smaller) recur for the left half
If none of it, the element isn't in the array

Why Binary search?

Study the table to understand why BS is better than the Linear Search!

Binary search works only if elements of the array are arranged in sorted order.

Linear search	Binary Search
The linear search starts searching from the first element and compares each element with a searched element till the element is not found	It finds the position of the searched element by finding the middle element of the array
The worst-case scenario for finding the element is O(n)	The worst-case scenario for finding the element is O(log2n)(beter!)
It is preferrable for the small-sized data sets	It is preferrable for the large-size data sets(better!)

Now we will try to implement the BS algorithm! Use hints if needed! Be careful with the tabulation!

Task

Set condition if the right is greater than the left.
Set the middle varible. The middle equals the left + (right - left) // 2.
Set condition if the element in the middle equals the x.
Perform recursion with the left part of the array if the x is greater than the middle element.
Perform recursion with the right part of the array if the x is lower than the middle element.

Task

Set condition if the right is greater than the left.
Set the middle varible. The middle equals the left + (right - left) // 2.
Set condition if the element in the middle equals the x.
Perform recursion with the left part of the array if the x is greater than the middle element.
Perform recursion with the right part of the array if the x is lower than the middle element.

Everything was clear?

Section 1. Chapter 1

BinarySearch 1/2

The main steps to implement the binary search algorithm:

Compare x(the desired item) with the middle element
If x matches with the middle element, we return the mid index
Else If x is greater than the mid element, then x can only lie in the right half subarray after the mid element
Else (x is smaller) recur for the left half
If none of it, the element isn't in the array

Why Binary search?

Study the table to understand why BS is better than the Linear Search!

Binary search works only if elements of the array are arranged in sorted order.

Linear search	Binary Search
The linear search starts searching from the first element and compares each element with a searched element till the element is not found	It finds the position of the searched element by finding the middle element of the array
The worst-case scenario for finding the element is O(n)	The worst-case scenario for finding the element is O(log2n)(beter!)
It is preferrable for the small-sized data sets	It is preferrable for the large-size data sets(better!)

Now we will try to implement the BS algorithm! Use hints if needed! Be careful with the tabulation!

Task

Set condition if the right is greater than the left.
Set the middle varible. The middle equals the left + (right - left) // 2.
Set condition if the element in the middle equals the x.
Perform recursion with the left part of the array if the x is greater than the middle element.
Perform recursion with the right part of the array if the x is lower than the middle element.

Task

Set condition if the right is greater than the left.
Set the middle varible. The middle equals the left + (right - left) // 2.
Set condition if the element in the middle equals the x.
Perform recursion with the left part of the array if the x is greater than the middle element.
Perform recursion with the right part of the array if the x is lower than the middle element.

Everything was clear?

The main steps to implement the binary search algorithm:

Compare x(the desired item) with the middle element
If x matches with the middle element, we return the mid index
Else If x is greater than the mid element, then x can only lie in the right half subarray after the mid element
Else (x is smaller) recur for the left half
If none of it, the element isn't in the array

Why Binary search?

Study the table to understand why BS is better than the Linear Search!

Binary search works only if elements of the array are arranged in sorted order.

Linear search	Binary Search
The linear search starts searching from the first element and compares each element with a searched element till the element is not found	It finds the position of the searched element by finding the middle element of the array
The worst-case scenario for finding the element is O(n)	The worst-case scenario for finding the element is O(log2n)(beter!)
It is preferrable for the small-sized data sets	It is preferrable for the large-size data sets(better!)

Now we will try to implement the BS algorithm! Use hints if needed! Be careful with the tabulation!

Task

Set condition if the right is greater than the left.
Set the middle varible. The middle equals the left + (right - left) // 2.
Set condition if the element in the middle equals the x.
Perform recursion with the left part of the array if the x is greater than the middle element.
Perform recursion with the right part of the array if the x is lower than the middle element.

Section 1. Chapter 1

Switch to desktop for real-world practiceContinue from where you are using one of the options below