Contenido del Curso
Binary Search in Python
Binary Search in Python
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!
Tarea
- Set condition if the
rightis greater than theleft. - Set the
middlevarible. Themiddleequals theleft + (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
xis greater than the middle element. - Perform recursion with the right part of the array if the
xis lower than the middle element.
Cambia al escritorio para practicar en el mundo realContinúe desde donde se encuentra utilizando una de las siguientes opciones¡Gracias por tus comentarios!
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!
Tarea
- Set condition if the
rightis greater than theleft. - Set the
middlevarible. Themiddleequals theleft + (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
xis greater than the middle element. - Perform recursion with the right part of the array if the
xis lower than the middle element.
Cambia al escritorio para practicar en el mundo realContinúe desde donde se encuentra utilizando una de las siguientes opciones¡Gracias por tus comentarios!
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!
Tarea
- Set condition if the
rightis greater than theleft. - Set the
middlevarible. Themiddleequals theleft + (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
xis greater than the middle element. - Perform recursion with the right part of the array if the
xis lower than the middle element.
Cambia al escritorio para practicar en el mundo realContinúe desde donde se encuentra utilizando una de las siguientes opciones¡Gracias por tus comentarios!
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!
Tarea
- Set condition if the
rightis greater than theleft. - Set the
middlevarible. Themiddleequals theleft + (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
xis greater than the middle element. - Perform recursion with the right part of the array if the
xis lower than the middle element.
Cambia al escritorio para practicar en el mundo realContinúe desde donde se encuentra utilizando una de las siguientes opcionesCambia al escritorio para practicar en el mundo realContinúe desde donde se encuentra utilizando una de las siguientes opciones