Posts tagged as “divide and conquer”

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

Follow up: Could you write an algorithm with O(log n) runtime complexity?

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Example 3:

Input: nums = [], target = 0
Output: [-1,-1]

Constraints:

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums is a non-decreasing array.
• -109 <= target <= 109

Idea:

Binary Search

Solution:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    let leftBound = -1;
    let rightBound = -1;
    let l = 0;
    let r = nums.length - 1;
    
    while (l <= r) {
        let mid = l + Math.floor((r - l) / 2);
        if (nums[mid] === target) {
            leftBound = mid;
            r = mid - 1;
        } else if (nums[mid] > target) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    
    l = 0;
    r = nums.length - 1;
    while (l <= r) {
        let mid = l + Math.floor((r - l) / 2);
        if (nums[mid] === target) {
            rightBound = mid;
            l = mid + 1;
        } else if (nums[mid] > target) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return [leftBound, rightBound];
};

There is an integer array nums sorted in ascending order (with distinct values).

Prior to 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,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 rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

Constraints:

• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• All values of nums are unique.
• nums is guaranteed to be rotated at some pivot.
• -104 <= target <= 104

Idea:

Binary Search: the idea is to create a recursive function that takes l and h as range in input and the key.

1) Find middle point mid = (l + h)/2
2) If key is present at middle point, return mid.
   Edge case check(not found): if (l > h) return -1;
3) Else If nums[l..mid] is sorted
    a) If key to be searched lies in range from nums[l]
       to nums[mid], recur for nums[l..mid].
    b) Else recur for nums[mid+1..h]
4) Else (nums[mid+1..h] must be sorted)
    a) If key to be searched lies in range from nums[mid+1]
       to nums[h], recur for nums[mid+1..h].
    b) Else recur for nums[l..mid] 

Solution:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    return searching(nums, 0, nums.length - 1, target);
};

function searching(nums, l, h, target) {
    // basic case: not found
    if (l > h) return -1;
    
    let mid = Math.floor((l + h) / 2);
    // basic case: found
    if (target === nums[mid]) return mid;
    
    // if nums[l...mid] is sorted
    if (nums[l] <= nums[mid]) { /// make sure is <=
        if (target >= nums[l] && target <= nums[mid])
            return searching(nums, l, mid - 1, target);
        else
            return searching(nums, mid + 1, h, target)
    }
    
    // if nums[l...mid] is notesorted, then nums[mid+1..h] must be sorted
    if (target >= nums[mid] && target <= nums[h])
        return searching(nums, mid + 1, h, target);
    else
        return searching(nums, l, mid - 1, target);
}