Problems Solved:
- #162 Find Peak Element
- #540 Single Element in a Sorted Array
This continues my daily series (Day 20: Binary Search mastery). Reaching a 20βday streak π₯ feels amazing β it marks nearly three weeks of consistent problem solving and deeper intuition for logarithmicβtime patterns.
π‘ What I Learned
Todayβs focus was on binary search beyond the basics:
- For Find Peak Element, I learned how to leverage binary search on an unsorted array by comparing
nums[mid]
andnums[mid+1]
. Depending on the slope, we can always guarantee the peak lies on one side, allowing logarithmic search. - For Single Element in a Sorted Array, the key trick is to use the pair alignment property: before the single element, pairs start at even indices; after it, pairs shift. Adjusting
mid
to be even ensures clean pair checks.
Both problems highlight how binary search can apply to more than just sorted lookups β itβs about shrinking the search space with a reliable invariant.
π§© #162 β Find Peak Element
Python (Slope check)
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] < nums[mid + 1]:
left = mid + 1
else:
right = mid
return left
Why it works: If nums[mid] < nums[mid+1]
, the slope goes upward, so a peak must exist on the right. Otherwise, the peak is on the left (possibly at mid
).
Time: O(log n)
Space: O(1)
C++ (Same slope idea)
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] < nums[mid + 1]) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
};
π§© #540 β Single Element in a Sorted Array
Python (Even index pairing)
class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if mid % 2 == 0:
if nums[mid] == nums[mid + 1]:
left = mid + 2
else:
right = mid
else:
if nums[mid] == nums[mid - 1]:
left = mid + 1
else:
right = mid
return nums[left]
Why it works: Before the single element, pairs align (even, odd)
. After it, alignment breaks. Checking nums[mid]
with its partner tells us which side to keep.
Time: O(log n)
Space: O(1)
C++ (Adjust mid to even)
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = (left + right) / 2;
if (mid % 2 == 1) mid--; // make mid even
if (nums[mid] == nums[mid + 1]) {
left = mid + 2;
} else {
right = mid;
}
}
return nums[left];
}
};
Why it works: By forcing mid
to even, we always check pairs (mid, mid+1)
. If they match, the single lies to the right; otherwise, itβs at or before mid
.
πΈ Achievements
- Find Peak Element: Understood how slope comparison can adapt binary search for unsorted arrays.
- Single Element in Sorted Array: Mastered the pairβalignment trick β a very elegant use of index parity.
π¦ Complexity Recap
-
Find Peak Element:
O(log n)
time,O(1)
space. -
Single Element in Sorted Array:
O(log n)
time,O(1)
space.
π£ Join the Journey
Day 20 streak achieved π. This milestone marks 3 weeks of coding discipline. Each dayβs problems are adding new insights into how binary search can be generalized far beyond its textbook form.
Follow along if youβre into algorithmic deep dives and clean implementations in Python and C++.
Links
- LinkedIn: https://www.linkedin.com/in/ertugrul-mutlu
- GitHub Series: https://github.com/Ertugrulmutlu/leetcode-series
Top comments (0)