🚀 Day 16 & Day 22 of #100DaysOfCode

🔄 𝗗𝗮𝘆 𝟭𝟲 – 𝟮𝟮: 𝗦𝗼𝗿𝘁𝗶𝗻𝗴 & 𝗕𝗶𝗻𝗮𝗿𝘆 𝗦𝗲𝗮𝗿𝗰𝗵 𝗗𝗲𝗲𝗽 𝗗𝗶𝘃𝗲

🧠 𝗧𝗼𝗽𝗶𝗰𝘀 𝗖𝗼𝘃𝗲𝗿𝗲𝗱: Sorting Algorithms + Binary Search Patterns

📚 𝗪𝗵𝗮𝘁 𝗜 𝗖𝗼𝘃𝗲𝗿𝗲𝗱:

🔹Reinforced basic sorting implementations: selection, insertion, and bubble sort

🔹Understood their behavior in sorted/nearly sorted arrays

🔹Explored merge sort and quick sort – identifying stability and in-place traits

🔹Practiced custom sorting using Python's sort() + key, and learned how it's handled in Java, C++, and JavaScript

🔹Learned binary search inside out, not just for finding a number but for solving boundary-based problems

🧠 𝗦𝗼𝗿𝘁𝗶𝗻𝗴 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺𝘀 – 𝗧𝗵𝗲 𝗖𝗼𝗿𝗲 𝗼𝗳 𝗢𝗿𝗱𝗲𝗿

𝗪𝗵𝘆 𝗦𝗼𝗿𝘁𝗶𝗻𝗴 𝗠𝗮𝘁𝘁𝗲𝗿𝘀

𝘚𝘰𝘳𝘵𝘪𝘯𝘨 𝘩𝘦𝘭𝘱𝘴 𝘪𝘮𝘱𝘳𝘰𝘷𝘦 𝘵𝘩𝘦 𝘦𝘧𝘧𝘪𝘤𝘪𝘦𝘯𝘤𝘺 𝘰𝘧 𝘮𝘢𝘯𝘺 𝘰𝘱𝘦𝘳𝘢𝘵𝘪𝘰𝘯𝘴 𝘢𝘯𝘥 𝘧𝘰𝘳𝘮𝘴 𝘵𝘩𝘦 𝘧𝘰𝘶𝘯𝘥𝘢𝘵𝘪𝘰𝘯 𝘰𝘧 𝘤𝘰𝘶𝘯𝘵𝘭𝘦𝘴𝘴 𝘢𝘭𝘨𝘰𝘳𝘪𝘵𝘩𝘮𝘴. 𝘉𝘶𝘪𝘭𝘵-𝘪𝘯 𝘴𝘰𝘳𝘵𝘴 𝘢𝘳𝘦 𝘤𝘰𝘯𝘷𝘦𝘯𝘪𝘦𝘯𝘵—𝘣𝘶𝘵 𝘶𝘯𝘥𝘦𝘳𝘴𝘵𝘢𝘯𝘥𝘪𝘯𝘨 𝘵𝘩𝘦 𝘪𝘯𝘯𝘦𝘳 𝘸𝘰𝘳𝘬𝘪𝘯𝘨𝘴 𝘴𝘩𝘢𝘳𝘱𝘦𝘯𝘴 𝘢𝘭𝘨𝘰𝘳𝘪𝘵𝘩𝘮𝘪𝘤 𝘵𝘩𝘪𝘯𝘬𝘪𝘯𝘨.

🔑𝗞𝗲𝘆 𝗦𝗼𝗿𝘁𝗶𝗻𝗴 𝗖𝗼𝗻𝗰𝗲𝗽𝘁𝘀:

🔹Stable Sort: Maintains relative order of equal elements

🔹In-place Sort: Uses constant auxiliary space

Time Complexity Awareness: Crucial for selecting the right sort for the right use case

🔹𝗕𝗮𝘀𝗶𝗰 𝗦𝗼𝗿𝘁𝗶𝗻𝗴 𝗜𝗺𝗽𝗹𝗲𝗺𝗲𝗻𝘁𝗮𝘁𝗶𝗼𝗻𝘀:

✅ Selection Sort – Repeatedly finds the minimum and swaps

👉Time: O(n²), In-place ✅, Not stable ❌

✅ Insertion Sort – Like sorting cards in hand

👉Time: Best O(n), Worst O(n²), Stable ✅, In-place ✅

✅ Bubble Sort – Adjacent swaps until sorted

👉Time: O(n²), Stable ✅, In-place ✅, Early exit optimization

🔹𝗔𝗱𝘃𝗮𝗻𝗰𝗲𝗱 𝗦𝗼𝗿𝘁𝗶𝗻𝗴:

✅ Merge Sort – Divide and conquer; recursively splits and merges

👉Time: O(n log n), Stable ✅, Not in-place ❌

✅ Quick Sort – Partition using a pivot

👉Time: Avg O(n log n), Worst O(n²), Not stable ❌, In-place ✅

🔹𝗕𝘂𝗶𝗹𝘁-𝗶𝗻 𝗦𝗼𝗿𝘁 & 𝗖𝘂𝘀𝘁𝗼𝗺 𝗖𝗼𝗺𝗽𝗮𝗿𝗮𝘁𝗼𝗿𝘀:

Learned to leverage Python's sort() and sorted() with custom key functions, and how other languages like Java, C++, and JavaScript handle custom sort logic.

🔍 𝗕𝗶𝗻𝗮𝗿𝘆 𝗦𝗲𝗮𝗿𝗰𝗵 – 𝗙𝗿𝗼𝗺 𝗕𝗮𝘀𝗶𝗰𝘀 𝘁𝗼 𝗕𝗼𝘂𝗻𝗱𝗮𝗿𝗶𝗲𝘀

🔹I began with classic binary search: shrinking search space by half.

🔹Then I explored boundary problems like "first true" or "first >= target", which require recording an index while searching.

🔹I learned about monotonic functions—where truth values switch from false to true at a boundary. Perfect for binary search!

Eventually, I used this approach to solve diverse problems: finding duplicates, rotated array minimum, mountain peaks, and more.

⏱️ 𝗧𝗶𝗺𝗲 𝗖𝗼𝗺𝗽𝗹𝗲𝘅𝗶𝘁𝘆: All binary search variants: O(log n)

🧠 𝘾𝙤𝙙𝙚 & 𝙋𝙧𝙤𝙗𝙡𝙚𝙢 𝙎𝙤𝙡𝙫𝙞𝙣𝙜

🚀 𝗕𝗶𝗻𝗮𝗿𝘆 𝗦𝗲𝗮𝗿𝗰𝗵 – 𝗙𝗶𝗻𝗱 𝗧𝗮𝗿𝗴𝗲𝘁 𝗶𝗻 𝗦𝗼𝗿𝘁𝗲𝗱 𝗔𝗿𝗿𝗮𝘆

🧠 𝗣𝗿𝗼𝗯𝗹𝗲𝗺: 𝘍𝘪𝘯𝘥 𝘵𝘩𝘦 𝘪𝘯𝘥𝘦𝘹 𝘰𝘧 𝘢 𝘵𝘢𝘳𝘨𝘦𝘵 𝘦𝘭𝘦𝘮𝘦𝘯𝘵 𝘪𝘯 𝘢 𝘴𝘰𝘳𝘵𝘦𝘥 𝘢𝘳𝘳𝘢𝘺

🚀𝗙𝗶𝗿𝘀𝘁 𝗧𝗿𝘂𝗲 𝗶𝗻 𝗕𝗼𝗼𝗹𝗲𝗮𝗻 𝗔𝗿𝗿𝗮𝘆

🧠 𝗣𝗿𝗼𝗯𝗹𝗲𝗺: 𝘍𝘪𝘯𝘥 𝘵𝘩𝘦 𝘧𝘪𝘳𝘴𝘵 𝘰𝘤𝘤𝘶𝘳𝘳𝘦𝘯𝘤𝘦 𝘰𝘧 𝘛𝘳𝘶𝘦 𝘪𝘯 𝘢 𝘴𝘰𝘳𝘵𝘦𝘥 𝘣𝘰𝘰𝘭𝘦𝘢𝘯 𝘢𝘳𝘳𝘢𝘺

🔍 𝗖𝗵𝗮𝗶𝗻 𝗼𝗳 𝗧𝗵𝗼𝘂𝗴𝗵𝘁:

🔹If arr[mid] is False, we discard left half.

🔹If it's True, store index and move right to mid - 1.

🚀 𝗙𝗶𝗿𝘀𝘁 𝗘𝗹𝗲𝗺𝗲𝗻𝘁 𝗡𝗼𝘁 𝗦𝗺𝗮𝗹𝗹𝗲𝗿 𝗧𝗵𝗮𝗻 𝗧𝗮𝗿𝗴𝗲𝘁

🧠 Problem: Find the index of the first element ≥ target

🔍 Chain of Thought:

🔹Think of this as a boundary between < target and ≥ target

🚀 𝗙𝗶𝗿𝘀𝘁 𝗢𝗰𝗰𝘂𝗿𝗿𝗲𝗻𝗰𝗲 𝗼𝗳 𝗧𝗮𝗿𝗴𝗲𝘁 𝗶𝗻 𝗗𝘂𝗽𝗹𝗶𝗰𝗮𝘁𝗲𝘀

🧠 Problem: Return first index of target in sorted array with duplicates

🔍 Chain of Thought:

🔹Save index on match, shrink right. Continue until first instance.

🚀 𝗦𝗾𝘂𝗮𝗿𝗲 𝗥𝗼𝗼𝘁 𝗘𝘀𝘁𝗶𝗺𝗮𝘁𝗶𝗼𝗻

🧠 Problem: Return the floor value of sqrt(n) without built-in sqrt

🔍 Chain of Thought:

🔹Binary search on [1, n] to find highest mid s.t. mid² ≤ n

🚀 𝗠𝗶𝗻𝗶𝗺𝘂𝗺 𝗶𝗻 𝗥𝗼𝘁𝗮𝘁𝗲𝗱 𝗦𝗼𝗿𝘁𝗲𝗱 𝗔𝗿𝗿𝗮𝘆

🧠 Problem: Find the index of the minimum in rotated sorted array

🔍 Chain of Thought:

🔹Boundary exists between values > last element and ≤ last element

🚀 𝗣𝗲𝗮𝗸 𝗼𝗳 𝗠𝗼𝘂𝗻𝘁𝗮𝗶𝗻 𝗔𝗿𝗿𝗮𝘆

🧠 Problem: Return index of peak in mountain array

🔍 Chain of Thought:

🔹If arr[mid] > arr[mid + 1], we are in descending zone (possible peak)

🚀 𝗡𝗲𝘄𝘀𝗽𝗮𝗽𝗲𝗿𝘀 𝗦𝗽𝗹𝗶𝘁

🧠 𝗣𝗿𝗼𝗯𝗹𝗲𝗺: Split newspapers across coworkers to minimize max time

🔍 𝗖𝗵𝗮𝗶𝗻 𝗼𝗳 𝗧𝗵𝗼𝘂𝗴𝗵𝘁:

🔹Binary search on time. Feasible check counts workers needed for time limit.

💡 𝗞𝗲𝘆 𝗧𝗮𝗸𝗲𝗮𝘄𝗮𝘆𝘀

🔸 Binary search isn’t just for searching values—it’s a framework for narrowing down answers in monotonic problems.

🔸 Sorting isn’t just a topic—it’s a tool that affects performance and correctness across algorithms.

🧩 This week was about not just returning—but returning stronger.

#100DaysOfCode #Sorting #BinarySearch #DSA #CodingChallenge #ProblemSolving #Python #TechLearning #AlgorithmicThinking