Another from the archives! (Can you tell I’m going through old notes?)
This one strikes me as an interesting exercise exploring that common hurdle of mixing up array-indexes and array-values. This is a nontrivial “array search” problem.
class Solution:
def peakIndexInMountainArray(self, arr: List[int]) -> int:
for i in range(1, len(arr)-1):
if arr[i] > arr[i-1] and arr[i] > arr[i+1]:
return i
Apparently, however, we’re obliged to use binary search and find it in log(N) time. The idea there is you check your index “locally”, and move right or left depending on which way the mountain says is “up”.
Why don’t they just call it binary search? The runtime requirement is a giveaway — and for people who are “fluent” enough with runtime complexity to understand O(lg n) but don’t yet know about binary search, you are a rare breed, I’d think.
So I’ll spare you the usual C++ std::algorithm implementation. I like this loop. I think a lesson where we really 100% understand the intuition behind binary search, and then having students actually implement it, could be a nice hour.
class Solution(object):
def searchInsert(self, nums, target):
lb = 0
ub = len(nums)
while lb < ub:
mid = (lb+ub)/2
#print(lb, mid, ub)
searchValue = nums[mid]
# Feels hacky... can we do something smarter?
if mid == lb:
assert(ub == lb + 1)
if searchValue < target:
return ub
return lb
if searchValue > target:
ub = mid
elif searchValue < target:
lb = mid
else:
return mid
#print("done", lb, ub)
assert(lb == ub)
return lb
Introductory notes on computer science and programming