RCS.101.a
Last updated
Last updated
Stack ζ―ι»θ ¦η§εΈδΈζηΊεΊη€ηθ³ζη΅ζ§οΌζζ LIFO (Last In, First Out) ηηΉζ§γ
Queue ζ―ι»θ ¦η§εΈδΈεΊη€ηθ³ζη΅ζ§οΌζζ FIFO (First In, First Out) ηηΉζ§γ
θηΎε―¦δΈηζιζ¦εΏ΅ζ₯θΏοΌMessage Queue εζ― Infrastructure ηζ¬ηε―¦ηΎγ
BFS is the first relatively advanced, yet power algorithm we get to study.
We start by introducing the essence of BFS via the classic Binary Tree Level Order Traversal.
Binary Search/Bisection Search is one of the fundamental algorithms in Computer Science. It describes the process of searching for a specific value in an ordered collection.
Still, it's one of the must error-prone DSA in implementing.
Not only it's tricky to get right, it's also hard to comprehend one's binary search implementation without context.
Binary Search - A Different Perspective (introduces the concept of partitioning)
Understanding Binary Tree's fundamentals & applications.
Learn the classic "Find Index of Given Target from Sorted Array" problem & implementing it.
Elevate your understanding, think binary search in the terms of "Partitioning" from now on. Then using this to deconstruct a few other ppl's code.
Binary Search can applied to the follow problem types
Conceptually similar to Template I
There could be no exact value to locate. While having to recognise the closest target(s). High likelihood having to memorisation (variable for candidate values), also there might not be a finite list given upfront.
Can be conceptualised using partitioning. (think in terms of ranges and anchors, not necessary indices)
The ultimate divide-and-conquer algorithm is, of course, binary search (reference)
E (note: just implement a regular stack with array, had limit language options)
E
M
M
E
E
E
M
M
E (note: just implement a regular stack with linked list, had limit language options)
E
E
M
Once your done with the basic understanding. Combing BFS with the knowledge of and , you'll now able to bridge yourself into the challenging-yet-exciting Shortest Path Finding problems.
M
M
M
M
