🟡Medium
540. Single Element in a Sorted Array

Company: 🔍📱✴️

📝Дан отсортированный массив, состоящий из целых чисел, где каждый элемент встречается ровно дважды, за исключением одного элемента, который встречается ровно один раз.

Верните элемент, который встречается только один раз. Реализуйте решение за O(logn) по времени и O(1) по памяти

💡: используйте тот факт, что длина массива всегда нечетная

#leetcode540 | #medium #binarysearch

🟡Medium
2560. House Robber IV

Company: 🚔📱📱

📝Дан массив чисел, представляющий собой последовательность домов, в каждом из которых есть деньги. Грабитель хочет ограбить ровно k домов, но он не может грабить два соседних дома подряд.

Способность грабителя — это максимальная сумма, которую он способен украсть из одного дома.

Верните минимальную способность грабителя, чтобы бы он смог ограбить k домов

💡: ищите минимальную способность в диапазоне [min(a), max(a)] и для каждой проверяйте, можно ли ограбить k домов

#leetcode2560 | #medium #binarysearch

🟡Medium
2226. Maximum Candies Allocated to K Children

Company: 🚔🔍📱

📝Дан массив candies, где каждый элемент — это количество конфет в одной куче. Каждую кучу можно делить на любые части, но объединять кучи нельзя.

Нужно раздать конфеты k детям так, чтобы каждый получил одинаковое количество. Каждому ребенку можно дать конфеты только из одной части кучи, при этом некоторые кучи могут остаться неиспользованными.

Верните максимальное количество конфет, которое может получить каждый ребенок

💡: ищите максимальную кучу в диапазоне [1, max(a)] и для каждой проверяйте, возможно ли собрать k таких куч

#leetcode2226 | #medium #binarysearch

🟡Medium
2300. Successful Pairs of Spells and Potions

Company: 🚔📱

📝Даны два положительных целочисленных массива spells и potions, где spells[i] представляет собой силу заклинания, а potions[i] представляет собой силу зелья.

Пара заклинания и зелья считается успешной, если произведение их сил составляет не менее заданного числа success.

Верните целочисленный массив answer, где answer[i] — количество зелий, которые составят успешную пару с заклинанием spells[i]

💡: для каждого заклинания ищите наименьшую силу зелья

#leetcode2300 | #medium #binarysearch

🟡Medium
1901. Find a Peak Element II

Company: 🚔📱🏢

📝Дана матрица m x n, в которой нет двух одинаковых соседних ячеек. Необходимо найти любой пиковый элемент и вернуть его координаты, как массив длины 2.

Пиковый элемент в матрице — это элемент, который строго больше всех своих соседних: слева, справа, сверху и снизу. Можно предположить, что вся матрица окружена внешним периметром со значением -1 в каждой ячейке.

Вам необходимо написать алгоритм, который будет работать за время O(m log(n)) или O(n log(m))

💡: ищите максимум в столбце mid, а затем проверяйте не является ли этот элемент пиком, если нет — передвиньте соответствующий указатель в сторону большего соседа

#leetcode1901 | #medium #binarysearch

🟡Medium
81. Search in Rotated Sorted Array II

Company: 🔍🏢📱

📝Дан отсортированный по неубыванию массив nums, который был повернут на неизвестное число позиций, при этом массив может содержать повторяющиеся элементы. Также дано целое число target.

Вернуть true, если target находится в nums

💡: с помощью mid и l определяйте отсортированную часть массива, при этом исключайте nums[l] == nums[mid]

#leetcode81 | #medium #binarysearch

🔴Hard
410. Split Array Largest Sum

Company: 📱🚔📱

📝Дан массив целых чисел nums и целое число k, разделите nums на k непустых подмассивов таким образом, чтобы наибольшая сумма любого подмассива была минимальной.

Верните минимальную наибольшую сумму разделения

💡: ищите минимальную сумму в диапазоне [max(nums), sum(nums)], при которой nums можно разбить на k подмассивов с суммой не больше этой величины

#leetcode410 | #hard #binarysearch

🔴Hard
1231. Divide Chocolate

Company: 🔍

📝У вас есть плитка шоколада, представленная массивом sweetness, где каждый элемент — это уровень сладости одного кусочка.

Вы хотите поделить шоколад на k + 1 частей, разрезав плитку k раз, при этом вы забираете себе наименее сладкий из полученных кусков. Ваша цель — максимизировать сладость этой наименьшей части, которую вы себе оставите.

Найдите максимальную общую сладость кусочка, которую вы можете получить, оптимально разрезав плитку шоколада

💡: проверяйте, можно ли разбить массив так, чтобы каждая из k + 1 частей была хотя бы сладости mid из диапазона поиска [min(a), sum(a)]

#leetcode1231 | #hard #binarysearch

🔴Hard
4. Median of Two Sorted Arrays

Company: 📱📱🔴

📝Даны два отсортированных массива nums1 и nums2 размером m и n соответственно, объедините их в один отсортированный массив и верните его медиану.

Напишите алгоритм со временем работы не хуже O(log (m+n))

💡: используя бинарный поиск по одному массиву, найдите такое количество элементов из него, которое вместе с дополняющим количеством из второго массива правильно формирует левую половину объединенных массивов

#leetcode4 | #hard #binarysearch

🖼Иллюстрация алгоритма к задаче 4

Пример: nums1 = [1,2,3,4,5], nums2 = [1,2,3,4,5,6,7]

#figure #binarysearch