JavaScript Program to Search a Target Value in a Rotated Array

Q: What is JavaScript Program to Search a Target Value in a Rotated Array?

In this article, we will learn JavaScript Program to Search a Target Value in a Rotated Array,This free Javascript tutorial for complete beginners will help you learn Javascript from scratch.

Javascript Program for Search an element in a sorted and rotated array

In this article, we are going to implement a JavaScript program to Search for a target value in a rotated array.

Table of Content

Using Binary Search
Using Linear Search
Using Recursive Function
Using Modified Binary Search with Pivot Detection

Using Binary Search

In this approach, we begin by locating the middle element of the array. Next, we determine whether the target element is greater or smaller. If it’s greater, we proceed with the second half; otherwise, we focus on the first half.

Syntax:

while (left <= right) {
}

Example: Implementation of the above approach.

Javascript

const searchInRotatedArray = 
    (inputArray,targetElement) => {
  let left = 0;
  let right = inputArray.length - 1;

  while (left <= right) {
      const mid = Math.floor(
          (left + right) / 2);
      if (inputArray[mid] === targetElement) {
          return mid}

      if (inputArray[left] <= inputArray[mid]) {
          if (targetElement >= inputArray[left] &&
              targetElement < inputArray[mid]) {
              right = mid - 1;} 
          else {
              left = mid + 1}} 
      else {
          if (
              targetElement > inputArray[mid] &&
              targetElement <= inputArray[right]) {
              left = mid + 1;} 
          else {
              right = mid - 1}}}

// Target not found
  return -1; 
};

const rotatedArray = [4, 5, 6, 7, 0, 1, 2,];
const targetElement = 1;
console.log(
    searchInRotatedArray(rotatedArray,targetElement));

Output

Using Linear Search

In this method, we iterate through the entire array using a loop. During each iteration, we verify if the current element matches the target element. If a match is found, we return the current iteration as the index.

Syntax:

if (arr[index] === targetElement) {
    return index;
}

Example: Implementation of the above appraoch.

Javascript

const searchInRotatedArray = 
    (inputArray,targetElement) => {
  for (let index = 0;index < inputArray.length;index++) {
      if (inputArray[index] === targetElement) {
          return index}}

  // Target not found
  return -1;
};

const rotatedArray = [4, 5, 6, 7, 0, 1, 2];
const target = 0;
console.log(searchInRotatedArray(rotatedArray, target));

Output

Using Recursive Function

In this method, similar to binary search, we divide the array into two halves: the left half and the right half. We then apply a recursive binary search within these halves.

Syntax:

return searchInRotatedArray( nums, target, left, mid - 1)

Example: Implementation of the above approach.

Javascript

const searchInRotatedArray = 
    ( nums, target, left = 0, right = nums.length - 1) => {
  if (left > right) {
    
    // Target not found
    return -1}

  const mid = Math.floor(
    (left + right) / 2);
  if (nums[mid] === target) {
    return mid}

  if (nums[left] <= nums[mid]) {
    if (target >= nums[left] &&
      target < nums[mid]) {
      return searchInRotatedArray( 
          nums , target , left , mid - 1 )}
    else {
      return searchInRotatedArray( 
          nums, target, mid + 1, right)}}
  else {
    if (target > nums[mid] && target <= nums[right]) {
      return searchInRotatedArray( 
          nums, target, mid + 1, right)}
    else {
      return searchInRotatedArray( 
          nums, target, left, mid - 1)}}};

const rotatedArray = [5, 6, 7, 8, 9, 10, 1, 2, 3];
const target = 3;
console.log(searchInRotatedArray(rotatedArray,target));

Output

Method 4: Using Modified Binary Search with Pivot Detection

In this approach, we first find the pivot index of the rotated array. The pivot index is the index where the rotation occurs. Once we have the pivot index, we can perform a modified binary search considering the pivot to determine the target element.

Find the pivot index:
- We initialize two pointers, left and right, pointing to the start and end of the array, respectively.
- While left is less than right, we find the middle element.
- If the middle element is greater than the element at the right pointer, it indicates that the pivot lies to the right of the middle element. So, we set left = mid + 1.
- Otherwise, the pivot lies to the left of the middle element or at the middle element itself. In this case, we set right = mid.
- After the loop, left will be pointing to the pivot index.
Perform modified binary search:
- Based on the value of the target element and the first element of the array, we determine whether to search in the left half or the right half of the array.
- We perform a binary search considering the pivot index to find the target element.

Example:

JavaScript

const searchInRotatedArray = (nums, target) => {
    let left = 0;
    let right = nums.length - 1;

    // Find the pivot index
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    const pivot = left;

    // Perform modified binary search
    left = 0;
    right = nums.length - 1;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const rotatedMid = (mid + pivot) % nums.length;
        if (nums[rotatedMid] === target) {
            return rotatedMid;
        } else if (nums[rotatedMid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
};

const rotatedArray = [5, 6, 7, 8, 9, 10, 1, 2, 3];
const target = 3;
console.log(searchInRotatedArray(rotatedArray, target));