Binary Search: Background & Python Code

Code below... Continuing our series investigating algorithms in Python, in this video we'll cover the Binary Search, a highly efficient searching technique that only applies under certain conditions. In the beginning of the video we'll go over the basics of the binary search, and later we'll open up our coding editor and actually implement the algorithm using Python.

References:

In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful. If the search ends with the remaining half being empty, the target is not in the array.
Binary search runs in at worst logarithmic time, making O(log n) comparisons, where n is the number of elements in the array, the O is Big O notation, and log is the logarithm. Binary search takes constant (O(1)) space, meaning that the space taken by the algorithm is the same for any number of elements in the array. Although specialized data structures designed for fast searching—such as hash tables—can be searched more efficiently, binary search applies to a wider range of problems.

[lamba]

Hi, I'm from Russia and there is no such good videos in russian YouTube. Thanks for explanation.

[xreed]

FYI, in cases of odd-numbered lists, passing a float wont work in Python 3.6+. You would have to convert the float to an integer first to get this to work (using int(), which will always round it down). Apparently it's ok in Python 2.7 as you demonstrated.

[yvonnegrealy]

Your videos are great Brian, really helpful. Keep up the good work!

[AlexandrBorschchev]

thank you so much bro. im watch your videos and theyre veryy helpful.

[BiswaRanjanNanda]

WOW.. you rock !! you just earned a subscriber mate.

[OcaOca]

midpoint calculation should use integer division operator //

[MicrobeHub]

I accidentally created this without know it existed

[Smileoasis]

My doubt is like,
When I'm searching for a number which is the 0th item of a 10000+ long list, then this binary search won't be effective right? 😁

[jl_woodworks]

Well, why would I want to implement binary search just to return a boolean when I can use "in" for that? Nice video, but I think it's weird to return a boolean instead of the target's index on the list.

[Neha_H]

Thanks, explanation is to the point. Can you let us know how to implement this with string data type? That is searching for a string in an array of strings.

[MahiAbrarAmer]

Thanks a bunch! Subscribed.
Btw can you do linked lists too? And maybe a few more from the cambridge A2 9608 syllabus ;-; theres so little resource for python on it..

[aadishjain]

TypeError: unsupported operand type(s) for /: 'list' and 'int'
im getting this error, plz help

[ManfSteell]

can you please post the code for python 3