Binary Search Others¶
Table of Contents¶
- 69. Sqrt(x) (Easy)
- 74. Search a 2D Matrix (Medium)
- 240. Search a 2D Matrix II (Medium)
- 2476. Closest Nodes Queries in a Binary Search Tree (Medium)
- 278. First Bad Version (Easy)
- 374. Guess Number Higher or Lower (Easy)
- 162. Find Peak Element (Medium)
- 1901. Find a Peak Element II (Medium)
- 852. Peak Index in a Mountain Array (Medium)
- 1095. Find in Mountain Array (Hard)
- 153. Find Minimum in Rotated Sorted Array (Medium)
- 154. Find Minimum in Rotated Sorted Array II (Hard)
- 33. Search in Rotated Sorted Array (Medium)
- 81. Search in Rotated Sorted Array II (Medium)
- 222. Count Complete Tree Nodes (Easy)
- 1539. Kth Missing Positive Number (Easy)
- 540. Single Element in a Sorted Array (Medium)
- 4. Median of Two Sorted Arrays (Hard)
- 1064. Fixed Point (Easy) 👑
- 702. Search in a Sorted Array of Unknown Size (Medium) 👑
- 2936. Number of Equal Numbers Blocks (Medium) 👑
- 1060. Missing Element in Sorted Array (Medium) 👑
- 1198. Find Smallest Common Element in All Rows (Medium) 👑
- 1428. Leftmost Column with at Least a One (Medium) 👑
- 1533. Find the Index of the Large Integer (Medium) 👑
- 2387. Median of a Row Wise Sorted Matrix (Medium) 👑
- 302. Smallest Rectangle Enclosing Black Pixels (Hard) 👑
69. Sqrt(x)¶
# Left Right Pointers
def mySqrt(x: int) -> int:
"""Returns the square root of a number."""
if x < 2:
return x
left, right = 0, x // 2
while left <= right:
mid = left + (right - left) // 2
if mid * mid <= x < (mid + 1) * (mid + 1):
return mid
elif mid * mid < x:
left = mid + 1
else:
right = mid - 1
x = 8
print(mySqrt(x)) # 2
#include <cassert>
using namespace std;
class Solution {
public:
int mySqrt(int x) {
if (x < 2) return x;
int left = 0, right = x / 2;
int mid = 0;
while (left <= right) {
mid = left + (right - left) / 2;
long long a = 1LL * mid * mid;
long long b = 1LL * (mid + 1) * (mid + 1);
if (a <= x && x < b) {
return mid;
} else if (a < x)
left = mid + 1;
else
right = mid - 1;
}
return right;
}
};
int main() {
Solution solution;
assert(solution.mySqrt(4) == 2);
assert(solution.mySqrt(8) == 2);
assert(solution.mySqrt(1999) == 44);
return 0;
}
74. Search a 2D Matrix¶
from typing import List
# Binary Search
def searchMatrix(matrix: List[List[int]], target: int) -> bool:
if not matrix or not matrix[0]:
return False
m, n = len(matrix), len(matrix[0])
left, right = 0, m * n - 1
while left <= right:
mid = left + (right - left) // 2
x = matrix[mid // n][mid % n]
if x < target:
left = mid + 1
elif x > target:
right = mid - 1
else:
return True
return False
if __name__ == "__main__":
matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]
target = 3
print(searchMatrix(matrix, target)) # True
240. Search a 2D Matrix II¶
from typing import List
# Matrix
def searchMatrix(matrix: List[List[int]], target: int) -> bool:
m, n = len(matrix), len(matrix[0])
i, j = 0, n - 1
while i < m and j >= 0:
if matrix[i][j] == target:
return True
elif matrix[i][j] < target:
i += 1
else:
j -= 1
return False
matrix = [
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30],
]
target = 20
print(searchMatrix(matrix, target)) # False
2476. Closest Nodes Queries in a Binary Search Tree¶
278. First Bad Version¶
"""
- Find the first bad version given a function `isBadVersion`.
"""
# Binary Search
def firstBadVersion(n: int) -> int:
left, right = 1, n
while left <= right:
mid = left + (right - left) // 2
if isBadVersion(mid):
right = mid - 1
else:
left = mid + 1
return left
def isBadVersion(version: int) -> bool:
pass
374. Guess Number Higher or Lower¶
162. Find Peak Element¶
1901. Find a Peak Element II¶
852. Peak Index in a Mountain Array¶
1095. Find in Mountain Array¶
153. Find Minimum in Rotated Sorted Array¶
154. Find Minimum in Rotated Sorted Array II¶
33. Search in Rotated Sorted Array¶
from typing import List
# Binary Search
def search(nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
nums = [4, 5, 6, 7, 0, 1, 2]
target = 0
print(search(nums, target)) # 4
81. Search in Rotated Sorted Array II¶
222. Count Complete Tree Nodes¶
from collections import deque
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
# Recursive
def countNodesRecursive(root: Optional[TreeNode]) -> int:
if not root:
return 0
num = 1 + countNodesRecursive(root.left) + countNodesRecursive(root.right)
return num
# Iterative
def countNodesIterative(root: Optional[TreeNode]) -> int:
if not root:
return 0
q = deque([root])
count = 0
while q:
n = len(q)
for _ in range(n):
node = q.popleft()
count += 1
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return count
# |------------|------- |---------|
# | Approach | Time | Space |
# |------------|--------|---------|
# | Recursive | O(n) | O(n) |
# | Iterative | O(n) | O(n) |
# |------------|--------|---------|
root = [1, 2, 3, 4, 5, 6]
root = build(root)
print(root)
# __1__
# / \
# 2 3
# / \ /
# 4 5 6
print(countNodesRecursive(root)) # 6
print(countNodesIterative(root)) # 6
1539. Kth Missing Positive Number¶
540. Single Element in a Sorted Array¶
4. Median of Two Sorted Arrays¶
from typing import List
# Brute Force
def findMedianSortedArraysBF(nums1: List[int], nums2: List[int]) -> float:
nums = sorted(nums1 + nums2)
n = len(nums)
if n % 2 == 0:
return (nums[n // 2 - 1] + nums[n // 2]) / 2
else:
return nums[n // 2]
# Binary Search
def findMedianSortedArraysBS(nums1: List[int], nums2: List[int]) -> float:
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
imin, imax, half_len = 0, m, (m + n + 1) // 2
while imin <= imax:
i = (imin + imax) // 2
j = half_len - i
if i < m and nums2[j - 1] > nums1[i]:
imin = i + 1
elif i > 0 and nums1[i - 1] > nums2[j]:
imax = i - 1
else:
if i == 0:
max_of_left = nums2[j - 1]
elif j == 0:
max_of_left = nums1[i - 1]
else:
max_of_left = max(nums1[i - 1], nums2[j - 1])
if (m + n) % 2 == 1:
return max_of_left
if i == m:
min_of_right = nums2[j]
elif j == n:
min_of_right = nums1[i]
else:
min_of_right = min(nums1[i], nums2[j])
return (max_of_left + min_of_right) / 2
# |--------------|-----------------|--------------|
# | Approach | Time | Space |
# |--------------|-----------------|--------------|
# | Brute Force | O((n+m)log(n+m))| O(n+m) |
# | Binary Search| O(log(min(n,m)))| O(1) |
# |--------------|-----------------|--------------|
nums1 = [1, 3]
nums2 = [2]
print(findMedianSortedArraysBF(nums1, nums2)) # 2.0
print(findMedianSortedArraysBS(nums1, nums2)) # 2.0