Binary Search | 7 Days, 3 LeetCode Problems a Day

1) 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.

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 <= 104
• -104 < nums[i], target < 104
• All the integers in nums are unique.
• nums is sorted in ascending order.

Solution:

var search = function(nums, target) {
     return nums.indexOf(target);
};

• indexOf() method is used to find the index of a specific element within an array. The index represents the position of the element in the array.

2) 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.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -104 <= matrix[i][j], target <= 104

Solution:

var searchMatrix = function(matrix, target) {
        return matrix.flat().includes(target);
};

• Matrix Flattening:

Explanation: Matrix flattening is the process of converting a multi-dimensional matrix into a one-dimensional array. It copies all the elements within the array into a single flattened array.

Usage: In this code, matrix.flat() is used to flatten a 2D matrix and transform it into a 1D array.

• Includes:

Explanation: The includes() method checks whether a specific element exists within an array. It queries whether the element is present in the array and returns either true or false as a result.

Usage: In this code, matrix.flat().includes(target) is used to check if the flattened array contains the target element. If the target element is found in the array, it returns true; otherwise, it returns false.

3) 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.

Example 1:

Input: piles = [3,6,7,11], h = 8
Output: 4

Example 2:

Input: piles = [30,11,23,4,20], h = 5
Output: 30

Example 3:

Input: piles = [30,11,23,4,20], h = 6
Output: 23

Constraints:

• 1 <= piles.length <= 104
• piles.length <= h <= 109
• 1 <= piles[i] <= 109

Solution:

var minEatingSpeed = function(piles, h) {
    let left = 1, right = Math.max(...piles);
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (piles.reduce((total, pile) => total + Math.ceil(pile / mid), 0) > h) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
};

• reduce function is used to apply a function against an accumulator and each element in the array (from left to right) to reduce it to a single value. In this solution, it is used to calculate the total hours required to finish eating all the bananas at a certain speed.
• Math.max()[1] static method returns the largest of the numbers given as input parameters, or -Infinity if there are no parameters.
• Math.floor()[2] static method always rounds down and returns the largest integer less than or equal to a given number.
• Math.ceil()[3] static method always rounds up and returns the smallest integer greater than or equal to a given number.
• You can read my second article for information about using while.

References:

[1]: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/max

[2]: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/floor

[3]: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/ceil