Explore

Binary Search problems

⁠

https://leetcode.com/problems/binary-search/⁠

⁠

class Solution:

def search(self, nums: List[int], target: int) -> int:

left, right = 0, len(nums) - 1

while left <= right:

midpoint = left + (right - left) // 2

if nums[midpoint] == target:

return midpoint

if nums[midpoint] < target:

left = midpoint + 1

else:

right = midpoint - 1

return -1

def search_right_most(self, nums, target):

first, last = 0, len(arr)

while first < last:

mid = left + (right - left) // 2

if nums[mid] <= target:

first = mid + 1

else:

last = mid

return last - 1

Binary Search Right Most

Наличие на литкоде: отсутствует

Имеется: отсортированный массив с повторяющимися элементами

Необходимо: найти самый правый индекс

Еще вариант: binary search left most

def binary_search_right_most(nums, target):

first, last = 0, len(nums)

stated = False

while first < last:

midpoint = (first + last) // 2

if nums[midpoint] <= target:

if nums[midpoint] == target:

stated = True

first = midpoint + 1

else:

last = midpoint

return last - 1 if stated else -1

arr = [0, 0, 0, 1, 1, 1, 2, 3, 4, 4, 5, 5, 5, 5]

print(binary_search_right_most(arr, 4)) # output >>> 9

print(binary_search_right_most(arr, 6)) # output >>> -1

⁠

https://leetcode.com/problems/search-in-rotated-sorted-array/⁠

⁠

Подход:

Смотрим является ли левая часть “нормальной”

Утверждаем, если target в левой части, если она “нормальная”, или в правой части, если она “нормальная”

Определение “нормальности”: если nums[mid] > nums[start], то левая часть отсортированная по возрастанию, точка перегиба в правой части (скрин 1)

⁠

Скрин 1.

https://leetcode.com/problems/search-in-rotated-sorted-array/Figures/33/33_small_mid.png⁠

⁠

Скрин 2.

https://leetcode.com/problems/search-in-rotated-sorted-array/Figures/33/33_big_mid.png⁠

⁠

class Solution:

def search(self, nums: List[int], target: int) -> int:

left, right = 0, len(nums) - 1

while left <= right:

midpoint = left + (right - left) // 2

if nums[midpoint] == target:

return midpoint

if nums[left] <= nums[midpoint]:

# the left part is sorted

if target < nums[midpoint] and target >= nums[left]:

# the target is in the sorted part

right = midpoint - 1

else:

left = midpoint + 1

else:

if target > nums[midpoint] and target <= nums[right]:

# the target is in the sorted part

left = midpoint + 1

else:

right = midpoint - 1

return -1

⁠

https://leetcode.com/problems/search-a-2d-matrix/⁠

⁠

class Solution:

def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:

rows = len(matrix)

if rows < 1:

return False

cols = len(matrix[0])

if cols < 1:

return False

left, right = 0, rows * cols - 1

while left <= right:

midpoint = left + (right - left) // 2

row = midpoint // cols

col = midpoint % cols

if matrix[row][col] == target:

return True

if matrix[row][col] < target:

left = midpoint + 1

else:

right = midpoint - 1

return False

⁠

https://leetcode.com/problems/search-a-2d-matrix-ii/⁠

⁠

Подход: идем из угла по “диагонали” к искомой точке (кратчайший путь)

class Solution:

def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:

rows = len(matrix)

if rows == 0:

return False

cols = len(matrix[0])

if cols == 0:

return False

row, col = 0, cols - 1

while row < rows and col > -1:

if matrix[row][col] == target:

return True

if matrix[row][col] > target:

col -= 1

else:

row += 1

return False

Want to print your doc?
This is not the way.

Try clicking the ··· in the right corner or using a keyboard shortcut (

CtrlP

) instead.