Grind 75 Question 8: Binary Search
A problem so easy I can’t believe it.
The Problem
Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.
You must write an algorithm with O(log n) runtime complexity.
The First Attempts
I literally open and solve this project while I’m at the park with my kids, start to finish 10 minutes max. My only snag is that I was a doofus and returned target instead of index. But here’s the whiteboarded code:
var search = function(nums, target) {
let index = -1
for(i=0; i<nums.length; i++){
if (nums[i] === target)
index = i;
}
return target;
};See? Doofus. Only now, typing it out and viewing it on an actual laptop, do I see the bit about O(n) time complexity. I think the way I’ve solved it
The Solution
It’s barely worth re-typing, because all that changes is target, which is replaced by index, but here it is:
var search = function(nums, target) {
let index = -1
for(i=0; i<nums.length; i++){
if (nums[i] === target)
index = i;
}
return index;
};What I Learned
- It feels good to be able to solve a Leetcode question just like that. Not too profound of a revelation, but also it sort of is? Like, I was able to just code this. It’s the simplest thing in the world, but hopefully the more I work at these Grind 75 questions and memorizing the 14 Leetcode patterns, the more I’ll be able to bust through questions like this one and the last.
I’ve previewed the next question and, hoo boy. Things are about to get rough. And I’m about to learn about graphs.
min
read
