The Binary Search Algorithm (+ Python Code Solution)

FAANG Coding Interviews / Data Structures and Algorithms / Leetcode

[@GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[@andrewhting]

No bro, I’m so lost. Can you break it down even further for us noobs 😭

[@nice-vf4rj]

​@andrewhting how would you search a sorted list of numbers? From start to end or divide and conquer

[@mujtabarehman5255]

In most other languages, its better to do "left + (right - left) // 2", which is equal to "(right + left) // 2", except it takes away the chance of integer overflow. In Python it doesn't matter since numbers can theoretically be as large as needed.

[@greensalad_1205]

Remember that the list MUST be sorted, otherwise it won't work

[@sealzz7376]

I was about to ask that too. Isn’t there a function for sorting it already in python?

[@400elochess]

​@@sealzz7376numpy's np.sort

[@aayushsamal2715]

@@sealzz7376 there is indeed... just remember to use it

[@mohammedadel7849]

This can also be done recursively, but then the space complexity increases.

[@pangzlab]

Nice video. Forgot one critical thing, it should be sorted first to be able to perform this operation.

[@GregHogg]

"Given a sorted list of numbers", yes indeed it does. Thank you

[@observer3987]

👍🏼 what's the step over this in terms of complexity?

[@okcomputer2112]

What

[@mujtabarehman5255]

O(log n), since the search space divides in half each time

[@putuadibrata]

please make another one, but the list is not sorted. Thank you

[@nigh_anxiety]

Then binary search isn't possible, and you have to do a linear search. Or, if you expect to search the list multiple times, sort it first and then do binary search as in the video. It's not worth sorting and doing binary search if you're only going to search once because the best sorting is O(n log n) and a linear search is just O(n).

[@putuadibrata]

@@nigh_anxietyok