- Published on
Leetcode Pattern 10 Binary Search
- Authors
- Name
- Yinhuan Yuan
Introduction
Binary search is one of the most elegant and efficient algorithms in computer science, renowned for its simplicity and speed. This algorithm is a staple in many programming challenges and interviews due to its effectiveness in searching sorted data. In this blog post, we’ll dive into the core principles of binary search, explore how it works, and examine some practical use cases and variations.
The traditional binary search is an algorithm that finds the position of a target value within a sorted array or list. It operates by repeatedly dividing the search interval in half. If the target value is less than the value in the middle of the interval, it narrows the search to the lower half. If the target value is greater, it narrows the search to the upper half. This process continues until the target value is found or the search interval is empty.
This method can be generalized for broader applications. First, we establish the search range, defined by a minimum and maximum value. In a typical binary search, this range spans from 0 to the length of the array. Within this range, there is a boundary: to the left of this boundary, a certain condition is not met; to the right, the condition is satisfied. If we can easily determine whether the condition is met for any value within the range, we can apply binary search to locate the boundary between the two sides in O(log(N)) time.
If a problem involves searching within a linear range and requires finding an extreme value or boundary where a condition is satisfied, binary search can be effectively used to quickly pinpoint this boundary.
Here are the code template for Python and TypeScript.
Python Template
def search(nums: List[int], target: int):
lo, hi = ....... # TBD
condition = lambda mid: ...... # TBD
while lo < hi:
mid = (lo + hi) // 2
# const mid = (lo + hi) >> 1;
if condition(mid):
hi = mid
else:
lo = mid + 1
return lo
TypeScript Template
function search(nums: number[], target: number): number {
const condition = (mid: number): boolean => .......; // TBD
let [lo, hi] = .......; // TBD
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (condition(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
if (nums[lo] === target) return lo;
return -1;
};
- Questions
- 704.Binary Search[easy]
- 35.Search Insert Position[easy]
- 744.Find Smallest Letter Greater Than Target[easy]
- 34.Find First and Last Position of Element in Sorted Array[medium]
- 702.Search in a Sorted Array of Unknown Size[medium]
- 69. Sqrt(x)[Easy]
- 367. Valid Perfect Square[Easy]
- 278. First Bad Version[Easy]
- 74. Search a 2D Matrix[Medium]
- 162. Find Peak Element[Medium]
- 33.Search in Rotated Sorted Array[Medium]
- 81.Search in Rotated Sorted Array II[Medium]
- 153.Find Minimum in Rotated Sorted Array[Medium]
- 154.Find Minimum in Rotated Sorted Array II[Hard]
- 275. H-Index II[Medium]
- 1011. Capacity To Ship Packages Within D Days[Medium]
- 410. Split Array Largest Sum[Hard]
- 875. Koko Eating Bananas[Medium]
- 1482. Minimum Number of Days to Make m Bouquets[Medium]
- 668. Kth Smallest Number in Multiplication Table[Hard]
- 719. Find K-th Smallest Pair Distance[Hard]
- 1201. Ugly Number III[Medium]
- 1283. Find the Smallest Divisor Given a Threshold[Medium]
- 222. Count Complete Tree Nodes[Easy]
- 240. Search a 2D Matrix II[Medium]
- 378. Kth Smallest Element in a Sorted Matrix[Medium]
- 2187. Minimum Time to Complete Trips[Medium]
- 1539.Kth Missing Positive Numnber[Easy]
- 1060. Missing Element in Sorted Array[Medium]
- 1891. Cutting Ribbons[Medium]
- 540. Single Element in a Sorted Array[Medium]
- 374. Guess Number Higher or Lower[Easy]
- 270. Closest Binary Search Tree Value[Easy]
- 658.Find K Closest Elements[Medium]
- Reference
Questions
704.Binary Search[easy]
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.
Solution: The search range is from 0 to the length of the sorted array. We can divide this range into two parts: on the left, the values are less than the target, and on the right, the values are greater than or equal to the target. Once we find the boundary between these two parts, we can check if the value at the boundary is the target or not.
class Solution:
def search(self, nums: List[int], target: int) -> int:
lo, hi = 0, len(nums)
condition = lambda mid: nums[mid] >= target
while lo < hi:
mid = (lo + hi) // 2
# const mid = (lo + hi) >> 1;
if condition(mid):
hi = mid
else:
lo = mid + 1
if lo < len(nums) and nums[lo] == target:
return lo
return -1
function search(nums: number[], target: number): number {
// Find the most left postion, whose value meets the condition.
const condition = (mid: number): boolean => nums[mid] >= target;
let [lo, hi] = [0, nums.length];
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (condition(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
if (nums[lo] === target) return lo;
return -1;
};
35.Search Insert Position[easy]
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.
Solution: Similar to the 704.Binary Search [easy], we can solve this problem by identifying the boundary between values that are less than the target and those that are equal to or greater than the target.
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
lo, hi = 0, len(nums)
condition = lambda mid: nums[mid] >= target
while lo < hi:
mid = (lo + hi) // 2
# const mid = (lo + hi) >> 1;
if condition(mid):
hi = mid
else:
lo = mid + 1
return lo
function searchInsert(nums: number[], target: number): number {
const condition = (mid: number): boolean => nums[mid] >= target;
let [lo, hi] = [0, nums.length];
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (condition(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
};
744.Find Smallest Letter Greater Than Target[easy]
You are given an array of characters letters that is sorted in non-decreasing order, and a character target. There are at least two different characters in letters.
Return the smallest character in letters that is lexicographically greater than target. If such a character does not exist, return the first character in letters.
Solution: This problem can be efficiently solved by employing a binary search approach to locate a specific boundary within the array. Our goal is to identify the dividing line between two groups of values:
- Values that are equal to or less than the target
- Values that are strictly greater than the target
class Solution:
def nextGreatestLetter(self, letters: List[str], target: str) -> str:
lo, hi = 0, len(letters)
condition = lambda mid: letters[mid] > target
while lo < hi:
mid = (lo + hi) // 2
# const mid = (lo + hi) >> 1;
if condition(mid):
hi = mid
else:
lo = mid + 1
if lo == len(letters):
return letters[0]
return letters[lo]
function nextGreatestLetter(letters: string[], target: string): string {
// const condition = (mid: number): boolean => letters[mid].charCodeAt(0) > target.charCodeAt(0);
const condition = (mid: number): boolean => letters[mid] > target;
let [lo, hi] = [0, letters.length];
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (condition(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
if (lo === letters.length) return letters[0];
return letters[lo];
};
34.Find First and Last Position of Element in Sorted Array[medium]
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
You must write an algorithm with O(log n) runtime complexity.
Solution: We can approach this problem by identifying two crucial boundaries:
The first boundary separates values less than the target from those equal to or greater than the target. The second boundary distinguishes between values equal to or less than the target and those greater than the target.
To find the range of the target element, we need to locate both these boundaries. The first boundary represents the starting position of the target element (if it exists in the array). The second boundary, when decreased by 1, gives us the ending position of the target element. By using a binary search algorithm twice - once for each boundary - we can efficiently pinpoint these positions. This approach allows us to handle cases where the target appears multiple times in the array, as well as when it's not present at all.
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def solver(condition):
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
# const mid = (lo + hi) >> 1;
if condition(mid):
hi = mid
else:
lo = mid + 1
return lo
left_index = solver(lambda mid: nums[mid] >= target)
right_index = solver(lambda mid: nums[mid] > target) - 1
# Check if the target is present at the found indices
if left_index < len(nums) and nums[left_index] == target:
return [left_index, right_index]
else:
return [-1, -1]
function searchRange(nums: number[], target: number): number[] {
const conditionFirst = (mid: number): boolean => nums[mid] >= target;
const conditionLast = (mid: number): boolean => nums[mid] > target;
const solver = (condition: (mid: number) => boolean): number => {
let [lo, hi] = [0, nums.length];
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (condition(mid)) {
hi = mid;
} else {
lo = lo + 1;
}
}
return lo;
}
const low = solver(conditionFirst);
const high = solver(conditionLast) - 1;
if (nums[low] !== target) return [-1, -1];
return [low, high];
};
702.Search in a Sorted Array of Unknown Size[medium]
This is an interactive problem.
You have a sorted array of unique elements and an unknown size. You do not have an access to the array but you can use the ArrayReader interface to access it. You can call ArrayReader.get(i) that:
returns the value at the ith index (0-indexed) of the secret array (i.e., secret[i]), or returns 231 - 1 if the i is out of the boundary of the array. You are also given an integer target.
Return the index k of the hidden array where secret[k] == target or return -1 otherwise.
You must write an algorithm with O(log n) runtime complexity.
Solution: This problem can be approached in a manner similar to "704. Binary Search" [Easy]. Our objective is to identify the boundary between two groups of values: those less than the target, and those equal to or greater than the target. We can employ a binary search algorithm to efficiently locate this boundary. The search range for this problem is between 0 and 10001 (10000 + 1). By using binary search, we can quickly narrow down this range to find the precise point where values transition from being less than the target to being equal to or greater than it.
class Solution:
def search(self, reader: 'ArrayReader', target: int) -> int:
lo, hi = 0, 10000 + 1
condition = lambda mid: reader.get(mid) >= target
while lo < hi:
mid = (lo + hi) // 2
if condition(mid):
hi = mid
else:
lo = mid + 1
return -1 if reader.get(lo) != target else lo
function search(reader: ArrayReader, target: number): number {
let [lo, hi] = [0, 10**4 + 1];
const condition = (mid: number): boolean => reader.get(mid) >= target;
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (condition(mid)) {
hi = mid;
} else {
lo = lo + 1;
}
}
if (reader.get(lo) === target) return lo;
return -1;
};
69. Sqrt(x)[Easy]
Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.
You must not use any built-in exponent function or operator.
For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.
Solution: This problem can be approached similarly to the "704. Binary Search" [Easy] problem. Our goal is to identify the boundary between two sets of values: those whose squares are less than or equal to the target, and those whose squares exceed the target. This boundary will lie somewhere between 0 and x + 1. We can use a binary search algorithm to efficiently locate this boundary. By doing so, we're essentially finding the largest integer whose square doesn't surpass the target value. This method allows us to narrow down the search range quickly, making it an optimal solution for this problem.
class Solution:
def mySqrt(self, x: int) -> int:
lo, hi = 0, x + 1 #
condition = lambda mid: mid * mid > x
while lo < hi:
mid = (lo + hi) // 2
if condition(mid):
hi = mid
else:
lo = mid + 1
return lo - 1 # lo is the most left value which meet mid * mid > x.
function mySqrt(x: number): number {
if (x <= 1 ) return x;
// Find the minimal integer whose square is greater than x.
const condition = (mid: number): boolean => mid * mid > x;
let [lo, hi] = [0, x];
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (condition(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo - 1;
};
367. Valid Perfect Square[Easy]
Given a positive integer num, return true if num is a perfect square or false otherwise.
A perfect square is an integer that is the square of an integer. In other words, it is the product of some integer with itself.
You must not use any built-in library function, such as sqrt.
Solution: Similar to "Sqrt(x)" (LeetCode problem 69), we find the square root of the number and then check if it forms a valid perfect square.
function isPerfectSquare(num: number): boolean {
const sqrt = mySqrt(num); // 69. Sqrt(x)[Easy]
return sqrt * sqrt === num;
};
278. First Bad Version[Easy]
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.
You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
Solution: The range is between 1 and n + 1, and we can use the isBadVersion function to find the point where the transition occurs from false to true.
class Solution:
def firstBadVersion(self, n: int) -> int:
lo, hi = 1, n + 1
while lo < hi:
mid = (lo + hi) // 2
if isBadVersion(mid):
hi = mid
else:
lo = mid + 1
return lo
var solution = function(isBadVersion: any) {
return function(n: number): number {
let [lo, hi] = [1, n + 1];
// const condition = (mid: number): boolean => isBadVersion(mid);
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (isBadVersion(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
};
};
74. Search a 2D Matrix[Medium]
You are given an m x n integer matrix matrix with the following two properties:
Each row is sorted in non-decreasing order. The first integer of each row is greater than the last integer of the previous row. Given an integer target, return true if target is in matrix or false otherwise.
You must write a solution in O(log(m * n)) time complexity.
Solution: This problem is similar to other binary search questions. The main difference is that we need to convert the middle index into a row and column index within the matrix.
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
rows, cols = len(matrix), len(matrix[0])
lo, hi = 0, rows * cols
condition = lambda mid: matrix[mid // cols][ mid % cols] >= target
while lo < hi:
mid = (lo + hi) // 2
if condition(mid):
hi = mid
else:
lo = mid + 1
return lo < rows * cols and matrix[lo // cols][ lo % cols] == target
function searchMatrix(matrix: number[][], target: number): boolean {
const m = matrix.length;
const n = matrix[0].length;
let [lo, hi] = [0, m * n];
const condition = (mid: number): boolean => {
const row = Math.floor(mid / n);
const col = mid % n;
return matrix[row][col] >= target;
};
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (condition(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
if (lo === m * n) return false;
const row = Math.floor(lo / n);
const col = lo % n;
return matrix[row][col] === target;
};
162. Find Peak Element[Medium]
A peak element is an element that is strictly greater than its neighbors.
Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.
You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.
You must write an algorithm that runs in O(log n) time.
Solution: A peak is the leftmost value in a non-increasing sequence. We can identify this boundary using the condition condition = lambda mid: mid == len(nums) - 1 or nums[mid] >= nums[mid + 1]. This condition helps us find the peak by checking if the current value is greater than or equal to the next value, or if it is the last element in the array.
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
lo, hi = 0, len(nums)
# Find the most left down slope.
condition = lambda mid: mid == len(nums) - 1 or nums[mid] >= nums[mid + 1]
while lo < hi:
mid = (lo + hi) // 2
if condition(mid):
hi = mid
else:
lo = mid + 1
return lo
function findPeakElement(nums: number[]): number {
let [lo, hi] = [0, nums.length];
// The peak is the leftest side of a decresing trend.
const condition = (mid: number): boolean => mid === nums.length - 1 || nums[mid] > nums[mid + 1];
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (condition(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
};
33.Search in Rotated Sorted Array[Medium]
There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
Solution: The solution involves two steps. In the first step, we use binary search to find the index of the minimum value. In the second step, we use this index as a shift to locate the target.
For the first step, the boundary is defined where values on the left side are always greater than or equal to nums[0], and values on the right side are always less than nums[0]. (The boundary can also be defined as where values on the left side are always greater than or equal to nums[nums.length - 1], and values on the right side are always less than nums[nums.length - 1].)
In the second step, we adjust for the shift by adding it to the index when searching for the target.
function search(nums: number[], target: number): number {
function findMinIndex(nums: number[]): number {
// Find the valley: the leftest side of the value which is smaller than nums[0].
let [lo, hi] = [0, nums.length];
const condition = (mid: number): boolean => {
return nums[mid] < nums[0];
};
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (condition(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
};
const n = nums.length;
const minIndex = findMinIndex(nums);
const condition = (mid: number): boolean => nums[mid % n] >= target;
let [lo, hi] = [minIndex, minIndex + n];
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (condition(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return nums[lo % n] === target ? lo % n : -1;
};
81.Search in Rotated Sorted Array II[Medium]
There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).
Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].
Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.
You must decrease the overall operation steps as much as possible.
Solution: Similar to "Search in Rotated Sorted Array" (LeetCode problem 33), we can find the solution in two steps. First, we locate the index of the minimum value, and second, we use this index as a shift to find the target.
In the first step, we address the edge case where the first and last values are the same. We increment the low pointer until we reach a value different from the first (or last) value. If no different value is found, it means all the values are the same, and we can simply check if this value equals the target. If a different value is found, we look for the leftmost index of the values that are less than or equal to the last value.
In the second step, we use the index found in the first step as an index shift to locate the target.
// Relate to 154.Find Minimum in Rotated Sorted Array II
function search(nums: number[], target: number): boolean {
function findMinIndex(nums: number[]): number {
const n = nums.length;
let [lo, hi] = [0, n];
if (nums[0] === nums[n - 1]) {
// Increase lo until it is different from nums[n - 1]
while (lo < n && nums[lo] === nums[0]) {
lo += 1;
}
// All same values
if (lo === n) return -1;
}
// The valley is the leftest side of the value less than last value.
const condition = (mid: number): boolean => nums[mid] <= nums[n - 1];
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (condition(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
};
const n = nums.length;
const minIndex = findMinIndex(nums);
// All same values
if (minIndex === -1) return target === nums[0];
const condition = (mid: number): boolean => nums[mid % n] >= target;
let [lo, hi] = [minIndex, minIndex + n];
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (condition(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return nums[lo % n] === target;
};
153.Find Minimum in Rotated Sorted Array[Medium]
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
[4,5,6,7,0,1,2] if it was rotated 4 times. [0,1,2,4,5,6,7] if it was rotated 7 times. Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
Given the sorted rotated array nums of unique elements, return the minimum element of this array.
You must write an algorithm that runs in O(log n) time.
Solution: The array can be divided into two parts: the left side, where the elements are greater than the last value, and the right side, where the elements are less than or equal to the last value. The boundary between these two parts is the index of the minimum value in the array.
function findMin(nums: number[]): number {
let [lo, hi] = [0, nums.length];
// The valley is the leftest side of the value less than last value.
const condition = (mid: number): boolean => nums[mid] <= nums[nums.length - 1];
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (condition(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return nums[lo];
};
154.Find Minimum in Rotated Sorted Array II[Hard]
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,4,4,5,6,7] might become:
[4,5,6,7,0,1,4] if it was rotated 4 times. [0,1,4,4,5,6,7] if it was rotated 7 times. Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
Given the sorted rotated array nums that may contain duplicates, return the minimum element of this array.
You must decrease the overall operation steps as much as possible.
Solution: As discussed in "Search in Rotated Sorted Array II" (LeetCode problem 81), there's an edge case where the first value is the same as the last value. To handle this, we can increment the low pointer until it points to a value different from the first (or last) value. If we cannot find a different value, it means all the values in the array are the same.
Once we find a different value, we can try to locate the leftmost index of the values that are less than or equal to the last value.
function findMin(nums: number[]): number {
const n = nums.length;
let [lo, hi] = [0, n];
if (nums[0] === nums[n - 1]) {
// Increase lo until it is different from nums[n - 1]
while (lo < n && nums[lo] === nums[0]) {
lo += 1;
}
// All same values
if (lo === n) return nums[0];
}
// The valley is the leftest side of the value less than last value.
const condition = (mid: number): boolean => nums[mid] <= nums[n - 1];
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (condition(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return nums[lo];
};
275. H-Index II[Medium]
Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper and citations is sorted in ascending order, return the researcher's h-index.
According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.
You must write an algorithm that runs in logarithmic time.
Solution: The search range is between 0 and citations.length. We can divide the array into two parts: the left part where citations[mid] < n - mid and the right part where citations[mid] >= n - mid. Since citations[mid] is sorted, values on the left side are smaller and values on the right side are larger. Additionally, n - mid is larger on the left side and smaller on the right side. The boundary position where these conditions change is the answer.
function hIndex(citations: number[]): number {
// Find the min (the leftist) index that citations[i] >= n - 1 - i + 1
const n = citations.length;
let [lo, hi] = [0, n];
const condition = (mid: number): boolean => citations[mid] >= n - 1 - mid + 1;
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (condition(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return n - 1 - lo + 1;
};
1011. Capacity To Ship Packages Within D Days[Medium]
A conveyor belt has packages that must be shipped from one port to another within days days.
The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.
Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.
Solution: The minimum capacity required is the maximum weight of a single package, as any capacity smaller than this would be insufficient to complete the work. The maximum capacity is the total weight, which would allow us to ship all packages in one day. We can divide the search range into two parts: on the left, where we cannot complete the work within days, and on the right, where we can complete the work within days.
The condition function determines if a given capacity is sufficient to complete the work. The goal is to find the minimal capacity that meets this requirement. We do this by adding weights one by one and checking if the cumulative weight exceeds the current capacity. If it does, we increment the count (representing the number of days needed) and reset the total weight.
function shipWithinDays(weights: number[], days: number): number {
const n = weights.length;
// Find the min capacity which can ship all weights within days.
const maxWeight = Math.max(...weights); // Ship with weights.length days
const totalWeight = weights.reduce((acc, cur) => acc + cur, 0); // Ship it with one day
let [lo, hi] = [maxWeight, totalWeight + 1];
const condition = (capacity: number): boolean => {
let count = 0;
let total = 0;
weights.forEach(weight => {
total += weight;
if (total > capacity) {
total = weight;
count += 1;
}
});
if (total > 0) {
count += 1;
}
return count <= days;
};
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (condition(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
};
410. Split Array Largest Sum[Hard]
Given an integer array nums and an integer k, split nums into k non-empty subarrays such that the largest sum of any subarray is minimized.
Return the minimized largest sum of the split.
A subarray is a contiguous part of the array.
Solution: As same as 1011. Capacity To Ship Packages Within D Days
// As same as 1011. Capacity To Ship Packages Within D Days
875. Koko Eating Bananas[Medium]
Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.
Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.
Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.
Return the minimum integer k such that she can eat all the bananas within h hours.
Solution: The minimum speed is 1 (Koko eats one banana at a time), while the maximum speed is the size of the largest pile (Koko eats an entire pile each hour). We divide the search range into two parts: on the left side, we cannot finish eating all the piles within h hours with the current speed, and on the right side, we can finish within h hours.
To determine if a given speed is sufficient, calculate the hours required to eat each pile as Math.ceil(pile / speed), then sum these hours. If the total is less than or equal to h, the speed is feasible; otherwise, it is not.
The boundary is the answer for this question.
function minEatingSpeed(piles: number[], h: number): number {
let [lo, hi] = [1, Math.max(...piles)];
const feasible = (speed: number): boolean => {
const hours = piles.map(pile => Math.ceil(pile / speed))
.reduce((acc, cur) => acc + cur, 0);
return hours <= h;
};
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (feasible(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
};
1482. Minimum Number of Days to Make m Bouquets[Medium]
You are given an integer array bloomDay, an integer m and an integer k.
You want to make m bouquets. To make a bouquet, you need to use k adjacent flowers from the garden.
The garden consists of n flowers, the ith flower will bloom in the bloomDay[i] and then can be used in exactly one bouquet.
Return the minimum number of days you need to wait to be able to make m bouquets from the garden. If it is impossible to make m bouquets return -1.
Solution: If the number of flowers is less than the required m bouquets and k adjacent flowers per bouquet, it is impossible to find a solution.
The minimum number of days is 1, and the maximum is the highest value in bloomDay plus 1. We divide the search range into two parts: on the left side, we can achieve the goal within days, and on the right side, we cannot.
To determine feasibility, we use a feasible function to simulate the flower-picking process by checking adjacent flowers. If a flower is ready, we increment the count cur; if not, we reset cur to 0. If cur reaches k, we reset it and increment the bouquet count. We then check if the total bouquet count is at least m.
function minDays(bloomDay: number[], m: number, k: number): number {
const n = bloomDay.length;
if (n < m * k) return -1;
const feasible = (days: number): boolean => {
let count = 0;
let cur = 0;
bloomDay.forEach(day => {
if (day <= days) {
cur += 1;
if (cur === k) {
cur = 0;
count += 1;
}
} else {
cur = 0;
}
});
return count >= m;
};
let [lo, hi] = [1, Math.max(...bloomDay) + 1];
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (feasible(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
};
668. Kth Smallest Number in Multiplication Table[Hard]
Nearly everyone has used the Multiplication Table. The multiplication table of size m x n is an integer matrix mat where mat[i][j] == i * j (1-indexed).
Given three integers m, n, and k, return the kth smallest element in the m x n multiplication table.
Solution: The search range is from 1 to m * n. We divide this range into two parts: on the left, the count of elements less than x is less than k, and on the right, the count is greater than or equal to k. We can use an enough function to check if there are at least k values less than or equal to a given x. The smallest value satisfying the enough function is the answer we seek.. To count the numbers which are less than x, we can go through the row one by one. It is the min value of Math.floor(x / i) (a part of row.) and n (the whole row).
function findKthNumber(m: number, n: number, k: number): number {
const feasible = (x: number): boolean => {
let count = 0;
for (let i = 1; i <= m; i++) {
// Each row either has n elements or x // i elements
count += Math.min(Math.floor(x / i), n);
}
return count >= k;
};
let [lo, hi] = [1, m * n];
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (feasible(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
};
719. Find K-th Smallest Pair Distance[Hard]
The distance of a pair of integers a and b is defined as the absolute difference between a and b.
Given an integer array nums and an integer k, return the kth smallest distance among all the pairs nums[i] and nums[j] where 0 <= i < j < nums.length.
Solution: First, we sort the array. The range for the pair distance is between 0 and the maximum value (nums[n - 1]) and the minimum value (nums[0]). We can create an enough function to determine if there are at least k pairs with distances less than or equal to a given distance. Using this function, we can find the boundary: on the left side, there are fewer than k pairs with distances less than or equal to the distance, and on the right side, there are more than k pairs. The boundary value is the answer we are seeking.
To implement the enough function, use a sliding window technique to count pairs with distances less than or equal to the given distance. Fix i and extend j as far as possible until the difference exceeds the distance. The count of valid pairs will be j - i - 1. Move i forward one step at a time and update the count accordingly.
function smallestDistancePair(nums: number[], k: number): number {
const enough = (distance: number): boolean => { // two pointers
let count = 0, i = 0, j = 0;
while (i < n || j < n) {
while (j < n && nums[j] - nums[i] <= distance) { // move fast pointer
j++;
}
count += j - i - 1; // count pairs
i++; // move slow pointer
}
return count >= k;
};
nums.sort((a, b) => a - b); // TypeScript sort needs a comparison function
const n = nums.length;
let lo = 0, hi = nums[n - 1] - nums[0];
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (enough(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
};
1201. Ugly Number III[Medium]
An ugly number is a positive integer that is divisible by a, b, or c.
Given four integers n, a, b, and c, return the nth ugly number.
Solution: The search range is between 1 and (10^10). This range is divided into two parts: on the left, the total number of ugly numbers (divisible by (a), (b), or (c)) is less than (n); on the right, the total number of ugly numbers is greater than or equal to (n).
We need an enough function that takes a number as input and calculates the number of ugly numbers less than this number. To achieve this, we will use the Greatest Common Divisor (GCD) to compute the Least Common Multiple (LCM) and then use the LCMs to determine the count of ugly numbers.
function nthUglyNumber(n: number, a: number, b: number, c: number): number {
function gcd(x: number, y: number): number {
while (y !== 0) {
let temp = y;
y = x % y;
x = temp;
}
return x;
}
const ab = a * b / gcd(a, b);
const ac = a * c / gcd(a, c);
const bc = b * c / gcd(b, c);
const abc = a * bc / gcd(a, bc);
function enough(num: number): boolean {
const total = Math.floor(num / a) + Math.floor(num / b) + Math.floor(num / c)
- Math.floor(num / ab) - Math.floor(num / ac) - Math.floor(num / bc)
+ Math.floor(num / abc);
return total >= n;
}
let lo = 1;
let hi = 10 ** 10;
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (enough(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
};
1283. Find the Smallest Divisor Given a Threshold[Medium]
Given an array of integers nums and an integer threshold, we will choose a positive integer divisor, divide all the array by it, and sum the division's result. Find the smallest divisor such that the result mentioned above is less than or equal to threshold.
Each result of the division is rounded to the nearest integer greater than or equal to that element. (For example: 7/3 = 3 and 10/2 = 5).
The test cases are generated so that there will be an answer.
Solution: The minimum value for the divisor is 1, and the maximum value is one more than the largest number in the array. We create an enough function that takes a divisor as input, divides each number in the array by this divisor, sums the results, and checks if the sum is less than or equal to the threshold. The search range is split into two parts: on the left side, the enough function returns false, and on the right side, it returns true.
function smallestDivisor(nums: number[], threshold: number): number {
const enough = (divisor: number): boolean => {
const result = nums.map(num => Math.ceil(num / divisor))
.reduce((acc, cur) => acc + cur, 0);
return result <= threshold;
};
let [lo, hi] = [1, Math.max(...nums) + 1];
while (lo < hi) {
const mid = Math.floor((hi + lo) / 2);
if (enough(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
};
222. Count Complete Tree Nodes[Easy]
Given the root of a complete binary tree, return the number of the nodes in the tree.
According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
Design an algorithm that runs in less than O(n) time complexity.
Solution:
- Calculate the tree height:
- Move to the leftmost path of the tree to determine the height
hof the tree.
- Move to the leftmost path of the tree to determine the height
- Binary Search on the Last Level:
- Use binary search to count the number of nodes in the last level.
- For a complete binary tree, the last level may not be completely filled. The nodes in the last level are numbered from
0to2^h - 1. - Perform a binary search on the index range
[0, 2^h - 1]to determine how many nodes exist on the last level.
function countNodes(root: TreeNode | null): number {
if (root === null) return 0;
// Function to compute the height of the tree
const getHeight = (root: TreeNode): number => {
let p = root;
let height = 0;
while (p.left !== null) {
height += 1;
p = p.left;
}
return height;
};
// Check if a node exists at idx (0-indexed) in the last level
const notExists = (idx: number): boolean => {
let node: TreeNode = root;
let [left, right] = [0, 2 ** height - 1];
for (let i = 0; i < height; i++) {
const mid = Math.floor((left + right) / 2);
if (idx <= mid) {
node = node.left;
right = mid;
} else {
node = node.right;
left = mid + 1;
}
}
return node === null;
};
const height = getHeight(root)
if (height === 0) return 1;
let [lo, hi] = [0, 2 ** height];
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (notExists(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return (2 ** height - 1) + lo;
};
240. Search a 2D Matrix II[Medium]
Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:
Integers in each row are sorted in ascending from left to right. Integers in each column are sorted in ascending from top to bottom.
Solution: This question is related to 378. Kth Smallest Element in a Sorted Matrix[Medium].
function searchMatrix(matrix: number[][], target: number): boolean {
const m = matrix.length;
const n = matrix[0].length;
// Top Right corn. It has the largest value in its row and has the smallest value in its column.
// If the target value is equal to the value in top right corner, return true;
// If the target value is greater than the value in top right corner,
// it means all values in this row is less than the target value; So all of them can be removed from search area.
// If the target value is smalelr than the value in top right corner,
// it means all values in this column are greater than the target value. So all them can be removed from search area.
// O(max(m, n))
let row = 0;
let col = n - 1;
while (row < m && col >= 0) {
if (matrix[row][col] === target) return true;
if (matrix[row][col] < target) {
row += 1;
} else {
col -= 1;
}
}
return false;
};
378. Kth Smallest Element in a Sorted Matrix[Medium]
Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the kth smallest element in the matrix.
Note that it is the kth smallest element in the sorted order, not the kth distinct element.
You must find a solution with a memory complexity better than O(n2).
Follow up:
Could you solve the problem with a constant memory (i.e., O(1) memory complexity)? Could you solve the problem in O(n) time complexity? The solution may be too advanced for an interview but you may find reading this paper fun.
function kthSmallest(matrix: number[][], k: number): number {
const n = matrix.length;
function feasible(x: number): boolean {
// Function to count the number of elements less than or equal to x
let count = 0;
let row = n - 1;
let col = 0;
while (row >= 0 && col < n) {
if (matrix[row][col] <= x) {
count += (row + 1);
col += 1;
} else {
row -= 1;
}
}
return count >= k;
}
let lo = matrix[0][0];
let hi = matrix[n - 1][n - 1];
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (feasible(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
2187. Minimum Time to Complete Trips[Medium]
You are given an array time where time[i] denotes the time taken by the ith bus to complete one trip.
Each bus can make multiple trips successively; that is, the next trip can start immediately after completing the current trip. Also, each bus operates independently; that is, the trips of one bus do not influence the trips of any other bus.
You are also given an integer totalTrips, which denotes the number of trips all buses should make in total. Return the minimum time required for all buses to complete at least totalTrips trips.
Solution: The search range for the time is between 1 and the maximum value of the time array multiplied by totalTrips. We divide this range into two parts: on the left side, we can only complete fewer than totalTrips, while on the right side, we can complete totalTrips or more. Given a time T, we calculate the number of trips each bus can make and sum them up. We then compare this total with totalTrips to determine whether the completed trips are equal to or greater than totalTrips.
function minimumTime(time: number[], totalTrips: number): number {
const feasible = (midTime: number): boolean => {
const trips = time.map(v => Math.floor(midTime / v))
.reduce((acc, cur) => acc + cur, 0);
return trips >= totalTrips;
};
let [lo, hi] = [1, Math.max(...time) * totalTrips];
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (feasible(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
};
1539.Kth Missing Positive Numnber[Easy]
Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.
Return the kth positive integer that is missing from this array.
function findKthPositive(arr: number[], k: number): number {
const nums = arr;
// Number of missing elements until 1
const missingCount = (index: number): number => nums[index] - 1 - 1 - (index - 0 - 1);
const n = nums.length;
// If k missing numbers are beyond the last element in nums
if (k > missingCount(n - 1)) {
return nums[n - 1] + k - missingCount(n - 1);
}
let [lo, hi] = [0, n];
// Binary search to find the position where the kth missing number should be
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (missingCount(mid) >= k) {
hi = mid;
} else {
lo = mid + 1;
}
}
// Find the exact kth missing number
if (lo === 0) return k;
return nums[lo - 1] + k - missingCount(lo - 1);
};
1060. Missing Element in Sorted Array[Medium]
Given an integer array nums which is sorted in ascending order and all of its elements are unique and given also an integer k, return the kth missing number starting from the leftmost number of the array.
Follow up: Can you find a logarithmic time complexity (i.e., O(log(n))) solution?
Solution: We first developed a function to find the count of missing numbers between nums[index] and nums[0]. The total number of numbers between these two elements is nums[index] - nums[0] - 1. The current number of elements in the array between these indices is index - 1. Therefore, the number of missing numbers is calculated as (nums[index] - nums[0] - index + 1).
If k is greater than missingCount(n - 1), it indicates that the missing number is located after the last element in the array. We can find it using the formula nums[n - 1] + k - missingCount(n - 1).
The search range is initially from 0 to n. We can divide the range into two parts: the left part and the right part. In the left part, the count of missing numbers is less than k. In the right part, the count of missing numbers is greater than or equal to k. We then use binary search to find the boundary.
class Solution:
def missingElement(self, nums: List[int], k: int) -> int:
def missing_count(index):
# Number of missing elements until nums[index]
return nums[index] - nums[0] - index
n = len(nums)
# If k missing numbers are beyond the last element in nums
if k > missing_count(n - 1):
return nums[-1] + k - missing_count(n - 1)
left, right = 0, n - 1
# Binary search to find the position where the kth missing number should be
while left < right:
mid = (left + right) // 2
if missing_count(mid) < k:
left = mid + 1
else:
right = mid
# Find the exact kth missing number
return nums[left - 1] + k - missing_count(left - 1)
// Similar to 1539.Kth Missing Positive Numnber[Easy]
function missingElement(nums: number[], k: number): number {
// Number of missing elements until nums[index]
const missingCount = (index: number): number => nums[index] - nums[0] - 1 - (index - 0 - 1);
const n = nums.length;
// If k missing numbers are beyond the last element in nums
if (k > missingCount(n - 1)) {
return nums[n - 1] + k - missingCount(n - 1);
}
let [lo, hi] = [0, n];
// Binary search to find the position where the kth missing number should be
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (missingCount(mid) >= k) {
hi = mid;
} else {
lo = mid + 1;
}
}
// Find the exact kth missing number
return nums[lo - 1] + k - missingCount(lo - 1);
};
1891. Cutting Ribbons[Medium]
You are given an integer array ribbons, where ribbons[i] represents the length of the ith ribbon, and an integer k. You may cut any of the ribbons into any number of segments of positive integer lengths, or perform no cuts at all.
For example, if you have a ribbon of length 4, you can: Keep the ribbon of length 4, Cut it into one ribbon of length 3 and one ribbon of length 1, Cut it into two ribbons of length 2, Cut it into one ribbon of length 2 and two ribbons of length 1, or Cut it into four ribbons of length 1. Your goal is to obtain k ribbons of all the same positive integer length. You are allowed to throw away any excess ribbon as a result of cutting.
Return the maximum possible positive integer length that you can obtain k ribbons of, or 0 if you cannot obtain k ribbons of the same length.
Solution: The search range for the length is between 0 and the maximum length plus 1. We can split this range into two parts: on the left side, it is possible to cut the ribbons to obtain at least k ribbons of the same length, while on the right side, it is impossible. We define a feasible function, which takes a length as input and checks whether it is possible to cut k ribbons of that length. We then find the minimum length where it becomes impossible to cut k ribbons. If we subtract 1 from this length, we get the maximum length at which it is possible to cut k ribbons of the same length.
function maxLength(ribbons: number[], k: number): number {
// Given a length: len, is impossible to cut k ribbons with length of len.
const feasible = (len: number): boolean => {
const count = ribbons.map(ribbon => Math.floor(ribbon / len))
.reduce((acc, cur) => acc + cur, 0);
return count < k;
};
let [lo, hi] = [0, Math.max(...ribbons) + 1];
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (feasible(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo - 1;
};
540. Single Element in a Sorted Array[Medium]
You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once.
Return the single element that appears only once.
Your solution must run in O(log n) time and O(1) space.
Solution: The search range is between 0 and n. We divide this range into two parts: on the left side, the total count of numbers starting from the second occurrence with the same value is even; on the right side, this count is odd. We define a condition function that consistently returns true on the right side of the search range. In this function, we first check if the current number is equal to the one before or after it. We then calculate the total count of numbers starting from the second occurrence to determine whether the number is on the left or right side of the search range. Finally, the boundary of left side and right side is the answer we are looking for.
function singleNonDuplicate(nums: number[]): number {
const n = nums.length;
let [lo, hi] = [0, n];
const condition = (mid: number): boolean => {
if (nums[mid] === nums[mid + 1]) {
const count = mid + 1 - 0 + 1;
return count % 2 !== 0;
} else if (nums[mid] === nums[mid - 1]) {
const count = mid - 0 + 1;
return count % 2 !== 0;
} else {// mid is the element which appears only once
return true;
}
};
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (condition(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return nums[lo];
};
374. Guess Number Higher or Lower[Easy]
We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I will tell you whether the number I picked is higher or lower than your guess.
You call a pre-defined API int guess(int num), which returns three possible results:
-1: Your guess is higher than the number I picked (i.e. num > pick). 1: Your guess is lower than the number I picked (i.e. num < pick). 0: your guess is equal to the number I picked (i.e. num == pick). Return the number that I picked.
Solution: The search range is from 1 to n + 1. We divide this range into two parts: on the left, the guess function returns 1 (indicating num < pick), and on the right, the guess function returns 0 or -1 (indicating num >= pick). The boundary where the transition occurs is the index where nums equals pick.
function guessNumber(n: number): number {
let [lo, hi] = [1, n + 1];
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (guess(mid) <= 0) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
};
270. Closest Binary Search Tree Value[Easy]
Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target. If there are multiple answers, print the smallest.
Solution: First, we convert the binary search tree into a sorted array. Then, we find the value in the array that is greater than or equal to the target, which splits the search range (from 0 to the length of the array) into two parts. Finally, we compare the boundary value with the index just before it to determine the answer.
function closestValue(root: TreeNode | null, target: number): number {
const treeToArray = (root: TreeNode | null): number[] => {
if (root === null) return [];
return [...treeToArray(root.left), ...[root.val], ...treeToArray(root.right)];
};
const nums = treeToArray(root);
let [lo, hi] = [0, nums.length];
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (nums[mid] >= target) {
hi = mid;
} else {
lo = mid + 1;
}
}
// lo, lo - 1
if (lo === 0) return nums[0];
if (Math.abs(nums[lo] - target) < Math.abs(nums[lo - 1] - target)) {
return nums[lo];
}
return nums[lo - 1];
};
658.Find K Closest Elements[Medium]
Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.
An integer a is closer to x than an integer b if:
|a - x| < |b - x|, or |a - x| == |b - x| and a < b
Solution: We want to find the most left boundary that x - arr[mid] > arr[mid + k] - x
class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
if len(arr) <= k:
return arr
# Binary search to find the starting point
left, right = 0, len(arr) - k
while left < right:
mid = left + (right - left) // 2
if x - arr[mid] > arr[mid + k] - x:
left = mid + 1
else:
right = mid
# Return the subarray of k elements starting from the found index
return arr[left:left+k]