Tasks

Modified Binary Search

Index	Task Name	Task Number	Difficulty	Link
1	Binary Search	704	Easy	Link
2	Search in Rotated Sorted Array	33	Medium	Link
3	Find Minimum in Rotated Sorted Array	153	Medium	Link
4	Find Peak Element	162	Medium	Link
5	Search in Rotated Sorted Array II	81	Medium	Link
6	Find First and Last Position of Element in Sorted Array	34	Medium	Link
7	Find K Closest Elements	658	Medium	Link
8	Divide Two Integers	29	Medium	Link
9	H-Index II	275	Medium	Link
10	Search a 2D Matrix II	240	Medium	Link
11	First Bad Version	278	Easy	Link
12	Random Pick with Weight	528	Medium	Link
13	Single Element in a Sorted Array	540	Medium	Link

// 33. Search in Rotated Sorted Array

// Time: O(log n) | Space: O(1)
var search = function(nums, target) {
    if (!nums.length) {
        return -1;
    }
    let left = 0;
    let right = nums.length - 1;
    while (left <= right) {
        // Middle point to divide arr into 2 parts.
        let mid = left + Math.floor((right - left) / 2);
        
        // At the end mid should point to the target element.
        if (nums[mid] === target) {
            return mid;
        }
        // If the left part is sorted.
        if (nums[left] <= nums[mid]) {
            // If target is in the left part.
            if (target < nums[mid] && target >= nums[left]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        // Right part is sorted.
        } else {
            // If target is in the right part.
            if (target > nums[mid] && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    // No target in the nums array.
    return -1;
};

/*
 * Modified Binary Search
 * -----------------------------
 * 1. Divide the array into two halves.
 * 2. If the left half is sorted:
 * 2.1. Check if the target lies in this range, and if it does, perform a binary search on this half for the target value.
 * 2.2. If the target does not lie in this range, move to the second half of the array.
 * 3. If the first half is not sorted, check if the target lies in the second half.
 * 3.1. If the target lies in this half, perform a binary search on this half for the target value.
 * 3.2. If the target does not lie in the second half, examine the first half.
 * 4. If the target value is not found at the end of this process, we return -1.
 * -----------------------------
 * Time: O(log n) | Space: O(1)
 */

// 81. Search in Rotated Sorted Array II

// Time: O(log n) | Space: O(1)
var search = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    
    // Iterate using binary search logic.
    while (left <= right) {
        // Skip duplicates from the left.
        while (left < right && nums[left] === nums[left + 1]) {
            left++;
        }
        // Skip duplicates from the right.
        while (left < right && nums[right] === nums[right - 1]) {
            right--;
        }
        // Get mid element.
        const mid = left + Math.floor((right - left) / 2);

        // Target found.
        if (nums[mid] === target) {
            return true;
        }
        // If left part is sorted.
        if (nums[mid] >= nums[left]) {
            // If target is in the left range.
            if (nums[mid] >= target && nums[left] <= target) {
                right = mid - 1;
            // Target is in the right range.
            } else {
                left = mid + 1;
            }
        // Right part is sorted.
        } else {
            // If target is in the right range.
            if (nums[mid] <= target && nums[right] >= target) {
                left = mid + 1;
            // Target is in the left range.
            } else {
                right = mid - 1;
            }
        }
    }
    // Target is not found in the array.
    return false;
};

// 658. Find K Closest Elements

// Time: O(log n) | Space: O(1)
var findClosestElements = function(arr, k, x) {
    let low = 0;
    let high = arr.length - 1;
    while (low < high) {
        const mid = Math.floor(low + (high - low) / 2);
        
        // Distance from mid to x.
        const leftVal = Math.abs(arr[mid] - x);
        
        // Distance from mid + k to x.
        const rightVal = Math.abs(arr[mid + k] - x);
        
        // If distance from mid is bigger then mid + k to x -> we might skip the left part.
        if (leftVal > rightVal) {
            low = mid + 1;
        // Else we might skip the right part.
        } else {
            high = mid;
        }
    }
    // Return from the closest one to the closest + k elements.
    return arr.slice(low, low + k);
};

/*
 * Binary Search
 * -------------------------------
 * 1. Go with left, right and mid to find the closest element to start with.
 * 2. Return sub-array starting from closest to closest + k elements.
 * -------------------------------
 * Time: O(log n) | Space: O(1)
 */

// 278. First Bad Version

// Time: O(log(n)) | Space: O(1)
var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
        let l = 1;
        let r = n;
        while (l < r) {
            let m = l + Math.floor((r - l) / 2);
            if (isBadVersion(m)) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    };
};

// 528. Random Pick with Weight

// Time: O(log n) | Space: O(n) 
var Solution = function(w) {
    this.arr = [];
    let sum = 0;
    // Calculating the weights running sums list
    for (let i = 0; i < w.length; i++) {
        sum += w[i];
        this.arr.push(sum);
    }
};

/**
 * @return {number}
 */
Solution.prototype.pickIndex = function() {
    let target = Math.random() * this.arr[this.arr.length - 1];
    
    // Assigning low pointer at the start of the array
    let low = 0;
    
    // Assigning high pointer at the end of the array
    let high = this.arr.length - 1;

    // Binary search to find the target
    while (low < high) {
        let mid = Math.floor(low + ((high - low) / 2));
        if (this.arr[mid] <= target) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return high;  
};

/*
 * Running Sums | Binary Search
 * ---------------------------------
 * 1. Create the "running sums" array to represent the probability ranges beween weight nums.
 * 2. To pick random -> create the random target between 0 and the biggest cummulative sum.
 * 3. Use binary search to search target in the running sums array.
 * 4. Return index of element that match the target.
 * ---------------------------------
 * Time: O(log n) | Space: O(n)
 */

// 540. Single Element in a Sorted Array

// Time: O(log n) | Space: O(1)
var singleNonDuplicate = function(nums) {
    let left = 0;
    let right = nums.length - 1;
    while (left < right) {
        let mid = Math.floor(left + (right - left) / 2);
        mid = mid % 2 ? mid - 1 : mid;
        if (nums[mid] !== nums[mid + 1]) {
            right = mid;
        } else {
            left = mid + 2;
        }
    }
    return nums[left];
};

/*
 * Binary Search
 * ----------------------------
 * 1. Calculate mid. If mid is odd -> mid - 1.
 * 2. If next after mid is not nums[mid] -> move right pointer.
 * 3. Else -> Move left pointer.
 * 4. Return nums[left].
 * ----------------------------
 * Time: O(log n) | Space: O(1)
 */