0704 - Binary Search (Easy)
Problem Link
https://leetcode.com/problems/binary-search/
Problem Statement
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.
Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
Example 2:
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1
Constraints:
1 <= nums.length <= 10^4-10^4 < nums[i], target < 10^4- All the integers in
numsare unique. numsis sorted in ascending order.
Approach 1: Brute Force/Linear Search
The questions asks for an time answer. But what if we can't find that. We can always start with the brute force solution first to gain insight. Obviously we can imagine, that if we scan through the numbers, we can return it if we find it, and if we reach the end of the array without finding it, we can return -1.
We also know the array is sorted, so if we ever pass the target before the end, we can return early. That is our insight right there.
Time Complexity to scan each number in the array.
Space Complexity
- Python
class Solution:
def search(self, nums: List[int], target: int) -> int:
# scan all numbers, tracking index, i and number, num.
for i, num in enumerate(nums):
# if num == target, we found num, return index, i
if num == target:
return i
# num > target, we passed it, we can return -1 early
elif num > target:
return -1
# if we couldn't find it and couldn't return early, return -1.
return -1
Note we found our insight above that the array is sorted. Since the array is sorted, and we know if the number we are looking at is larger or smaller than our target, then can we eliminate the need to look at all the numbers? Can we look directly in the middle, and eliminate half of all numbers in one go? We can. That is our intuition for binary search below.
Approach 2: Binary Search
We set the boundary from the first index to the last index of the array. In each round, we try the middle one . The reason we add here is that we need to take the upper one if there are even number of elements. If the target is less than , then move the right pointer to , else move the left pointer to . At the end, if the target is found, the index would be .
- C++
- Python
- JavaScript
class Solution {
public:
int search(vector<int>& nums, int target) {
// init possible boundary
int n = nums.size(), l = 0, r = n - 1;
while (l < r) {
// get the middle one
// for even number of elements, take the upper one
int m = l + (r - l + 1) / 2;
// exclude m
if (target < nums[m]) r = m - 1;
// include m
else l = m;
}
return nums[l] == target ? l : -1;
}
};
class Solution:
def search(self, nums: List[int], target: int) -> int:
# initialize left, l and right, r boundaries
l, r = 0, len(nums)-1
# l passes r, we are done.
while l < r:
# get our middle number, right one if even number elements.
# note: do it this way to prevent int overflow, don't have
# issue in Pythonn, but it is good practice for languages that do.
m = l + (r-l+1) // 2
# target smaller than we are looking at.
if nums[m] > target:
# set boundary m-1 to keep scanning left half
r = m - 1
else:
# set boundary to m to keep scanning right half
l = m
# if we found the item, it will be @ index l, else -1.
return l if nums[l] == target else -1
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function(nums, target) {
// initialize left and right boundary
let l = 0;
let r = nums.length - 1;
while (l <= r) {
// find mid value
let mid = Math.floor((l + r) / 2)
if (nums[mid] == target) return mid;
// if mid value is greater than target
// search left
else if (nums[mid] > target) r = mid - 1;
// if mid value is less than target
// search right
else l = mid + 1;
}
return -1;
};
How about taking the lower element if the number of elements is even?
Similarly, we set the boundary from the first index to the last index of the array. In each round, we try the middle one . If there are even number of elements, we take the lower one. If the target is greater than , then move the left pointer to , else move the right pointer to . At the end, if the target is found, the index would be .
- C++
- Python
- JavaScript
class Solution {
public:
int search(vector<int>& nums, int target) {
// init possible boundary
int n = nums.size(), l = 0, r = n - 1;
while (l < r) {
// get the middle one
// for even number of elements, take the lower one
int m = l + (r - l) / 2;
// exclude m
if (target > nums[m]) l = m + 1;
// include m
else r = m;
}
return nums[l] == target ? l : -1;
}
};
class Solution:
def search(self, nums: List[int], target: int) -> int:
# initialize left, l and right, r boundaries
l, r = 0, len(nums)-1
# l passes r, we are done.
while l < r:
# get our middle number, left one if even number elements.
# note: do it this way to prevent int overflow, we don't have the
# issue in Python, but it is good practice for languages that do.
m = l + (r-l) // 2
# target larger than num we are looking at.
if nums[m] < target:
# set boundary m-1 to keep scanning right half
l = m + 1
else:
# set boundary to m to keep scanning left half
r = m
# if we found the item, it will be @ index l, else -1.
return l if nums[l] == target else -1
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function(nums, target) {
// initialize left and right boundary
let l = 0;
let r = nums.length - 1;
while (l <= r) {
// find mid value
let mid = Math.floor((l + r) / 2)
if (nums[mid] == target) return mid;
// if mid value is less than target
// search right
else if (nums[mid] < target) l = mid + 1;
// if mid value is greater than target
// search left
else r = mid - 1;
}
return -1;
};