array/search-in-rotated-sorted-array.js

"use strict";
/**
 * <b>LeetCode -  Array Problems</b>
 *
 * @example
 * import { searchInRotatedArray } from '../../array';
 *
 * console.log(searchInRotatedArray([4,5,6,7,0,1,2], 0)); // 4
 *
 * @author Gaurav Soni
 *
 * @module array
 *
 */
Object.defineProperty(exports, "__esModule", { value: true });
exports.searchWithOneBinarySearch = exports.searchWithPivotAndShift = exports.searchInRotatedArray = void 0;
/**
 * @public
 *
 * <b>Time Complexity:</b> O(log(n)) <br />
 *
 * @see {@link https://leetcode.com/problems/search-in-rotated-sorted-array/|Search in rotated array}
 *
 * @param {number[]} nums array of numbers.
 * @param {number} target element to be searched.
 * @returns {number} Index of element otherwise -1
 */
function searchInRotatedArray(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    const n = nums.length;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] > nums[n - 1]) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    const index = binarySearch(0, left - 1);
    return index !== -1 ? index : binarySearch(left, n - 1);
    function binarySearch(left, right) {
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            if (target == nums[mid])
                return mid;
            if (target < nums[mid]) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        return -1;
    }
}
exports.searchInRotatedArray = searchInRotatedArray;
function searchWithPivotAndShift(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    const n = nums.length;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] > nums[n - 1]) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    return binarySearch(left);
    function binarySearch(pivot) {
        const n = nums.length;
        let left = 0;
        let right = n - 1;
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            if (target == nums[(pivot + mid) % n])
                return (pivot + mid) % n;
            if (target < nums[(pivot + mid) % n]) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        return -1;
    }
}
exports.searchWithPivotAndShift = searchWithPivotAndShift;
function searchWithOneBinarySearch(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (target == nums[mid])
            return mid;
        if (nums[left] <= nums[mid]) {
            if (target < nums[left] || target > nums[mid]) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        else {
            if (target > nums[right] || target < nums[mid]) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
    }
    return -1;
}
exports.searchWithOneBinarySearch = searchWithOneBinarySearch;