{"@context":"https://schema.org","@type":"TechArticle","headline":"Search in Rotated Sorted Array Algorithm - Visualization & Solution","description":"There is an integer array nums sorted in ascending order (with distinct values).\n\nPrior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= 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].\n\nGiven the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.\n\nYou must write an algorithm with O(log n) runtime complexity.\n\nExample 1:\nInput: nums = [4,5,6,7,0,1,2], target = 0\nOutput: 4\n\nExample 2:\nInput: nums = [4,5,6,7,0,1,2], target = 3\nOutput: -1\n\nExample 3:\nInput: nums = [1], target = 0\nOutput: -1\n\nConstraints:\n• 1 <= nums.length <= 5000\n• -10^4 <= nums[i] <= 10^4\n• All values of nums are unique.\n• nums is an ascending array that is possibly rotated.\n• -10^4 <= target <= 10^4","image":"https://rulcode.com/og-image.png","inLanguage":"en","datePublished":"2025-12-01T16:02:45.271431+00:00","dateModified":"2026-05-30T07:30:42.245845+00:00","category":"Array, Binary Search","author":{"@type":"Organization","name":"Rulcode.com Team","url":"https://rulcode.com"},"publisher":{"@type":"Organization","name":"Rulcode.com","logo":{"@type":"ImageObject","url":"https://rulcode.com/android-chrome-512x512.png"}},"mainEntityOfPage":{"@type":"WebPage","@id":"https://rulcode.com/problem/search-in-rotated-sorted-array"},"about":{"@type":"Thing","name":"Search in Rotated Sorted Array","description":"There is an integer array nums sorted in ascending order (with distinct values).\n\nPrior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= 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].\n\nGiven the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.\n\nYou must write an algorithm with O(log n) runtime complexity.\n\nExample 1:\nInput: nums = [4,5,6,7,0,1,2], target = 0\nOutput: 4\n\nExample 2:\nInput: nums = [4,5,6,7,0,1,2], target = 3\nOutput: -1\n\nExample 3:\nInput: nums = [1], target = 0\nOutput: -1\n\nConstraints:\n• 1 <= nums.length <= 5000\n• -10^4 <= nums[i] <= 10^4\n• All values of nums are unique.\n• nums is an ascending array that is possibly rotated.\n• -10^4 <= target <= 10^4"},"proficiencyLevel":"intermediate","hasPart":[{"@context":"https://schema.org","@type":"SoftwareSourceCode","programmingLanguage":"python","codeSampleType":"optimize","text":"def search(nums: List[int], target: int) -> int:\n # Initialize left and right pointers to the start and end of the array.\n left, right = 0, len(nums) - 1\n \n # Perform binary search while the left pointer is less than or equal to the right pointer.\n while left <= right:\n # Calculate the middle index.\n mid = (left + right) // 2\n \n # If the element at the middle index is equal to the target, return the middle index.\n if nums[mid] == target:\n return mid\n \n # Determine which half of the array is sorted.\n if nums[left] <= nums[mid]:\n # The left half is sorted.\n # If the target is within the sorted left half.\n if nums[left] <= target < nums[mid]:\n # Move the right pointer to the element before the middle element.\n right = mid - 1\n else:\n # Move the left pointer to the element after the middle element.\n left = mid + 1\n else:\n # The right half is sorted.\n # If the target is within the sorted right half.\n if nums[mid] < target <= nums[right]:\n # Move the left pointer to the element after the middle element.\n left = mid + 1\n else:\n # Move the right pointer to the element before the middle element.\n right = mid - 1\n \n # If the target is not found, return -1.\n return -1","description":"

\n Intuition:
\n The array is sorted but rotated at some pivot. Even after rotation, at least\n one half of the array is always sorted. By identifying the sorted half and\n checking whether the target lies within it, we can discard half of the search\n space at each step using binary search.\n

\n\n

\n This allows us to search efficiently without scanning every element, even\n though the array is not fully sorted.\n

\n\n

\n Step-by-step thinking:\n

\n\n

Initialize two pointers: left at the start and right at the end of the array.
While left is less than or equal to right:

Compute the middle index mid.
If nums[mid] equals the target, return mid.
Check which half of the array is sorted.
If the left half is sorted, verify whether the target lies within it.
If it does, move right to mid - 1; otherwise move left to mid + 1.
If the right half is sorted, verify whether the target lies within it.
If it does, move left to mid + 1; otherwise move right to mid - 1.

If the loop ends without finding the target, return -1.

\n\n

\n Time Complexity: O(log n)
\n Space Complexity: O(1)
\n

\n"},{"@context":"https://schema.org","@type":"SoftwareSourceCode","programmingLanguage":"python","codeSampleType":"brute-force","text":"def search(nums, target):\n # Loop through every element in the array\n for i in range(len(nums)):\n\n # If the current element matches the target\n if nums[i] == target:\n # Return the index where the target is found\n return i\n\n # Target was not found in the array\n return -1","description":"

\n Intuition:
\n The simplest way to find a target value is to check each element one by one\n until the target is found. Since there is no information about the order of\n the array, every element must be examined.\n

\n\n

\n This approach is similar to searching for a word in a book by reading each\n page sequentially until you find the correct one.\n

\n\n

\n Step-by-step thinking:\n

\n\n

Start from the first element of the array.
Compare the current element with the target value.
If they match, return the current index.
If they do not match, move to the next element.
Repeat this process until the end of the array.

\n\n

\n If the target is not found after checking all elements, return -1.\n

\n\n

\n Why this is slow:
\n In the worst case, the target is either at the very end of the array or not\n present at all. This forces the algorithm to check every element, which\n becomes inefficient for large arrays.\n

"},{"@context":"https://schema.org","@type":"SoftwareSourceCode","programmingLanguage":"python","codeSampleType":"starter","text":"def search(nums: List[int], target: int) -> int:\n # TODO: Implement the search algorithm here.\n pass\n","description":"Search in Rotated Sorted Array implementation in python"},{"@context":"https://schema.org","@type":"SoftwareSourceCode","programmingLanguage":"java","codeSampleType":"optimize","text":"public static class Solution {\n public int search(int[] nums, int target) {\n int left = 0, right = nums.length - 1; // Initialize left and right pointers for binary search.\n\n while (left <= right) { // Continue searching while the left pointer is less than or equal to the right pointer.\n int mid = left + (right - left) / 2; // Calculate the middle index to avoid potential overflow.\n\n if (nums[mid] == target) { // If the middle element is the target, return the middle index.\n return mid;\n }\n\n // Determine which half is sorted\n if (nums[left] <= nums[mid]) { // Check if the left half is sorted.\n // Left half is sorted\n if (nums[left] <= target && target < nums[mid]) { // If the target is within the sorted left half.\n right = mid - 1; // Move the right pointer to search in the left half.\n } else { // If the target is not in the sorted left half.\n left = mid + 1; // Move the left pointer to search in the right half.\n }\n } else { // If the left half is not sorted, then the right half must be sorted.\n // Right half is sorted\n if (nums[mid] < target && target <= nums[right]) { // If the target is within the sorted right half.\n left = mid + 1; // Move the left pointer to search in the right half.\n } else { // If the target is not in the sorted right half.\n right = mid - 1; // Move the right pointer to search in the left half.\n }\n }\n }\n\n return -1; // If the target is not found, return -1.\n }\n}","description":"

\n\n

\n This allows us to search efficiently without scanning every element, even\n though the array is not fully sorted.\n

\n\n

\n Step-by-step thinking:\n

\n\n

Initialize two pointers: left at the start and right at the end of the array.
While left is less than or equal to right:

Compute the middle index mid.
If nums[mid] equals the target, return mid.
Check which half of the array is sorted.
If the left half is sorted, verify whether the target lies within it.
If it does, move right to mid - 1; otherwise move left to mid + 1.
If the right half is sorted, verify whether the target lies within it.
If it does, move left to mid + 1; otherwise move right to mid - 1.

If the loop ends without finding the target, return -1.

\n\n

\n Time Complexity: O(log n)
\n Space Complexity: O(1)
\n

\n"},{"@context":"https://schema.org","@type":"SoftwareSourceCode","programmingLanguage":"java","codeSampleType":"brute-force","text":"public static class Solution {\n public int search(int[] nums, int target) {\n\n // Loop through every element in the array\n for (int i = 0; i < nums.length; i++) {\n\n // If the current element matches the target\n if (nums[i] == target) {\n\n // Return the index where the target is found\n return i;\n }\n }\n\n // Target was not found in the array\n return -1;\n }\n}","description":"

\n\n

\n This approach is similar to searching for a word in a book by reading each\n page sequentially until you find the correct one.\n

\n\n

\n Step-by-step thinking:\n

\n\n

Start from the first element of the array.
Compare the current element with the target value.
If they match, return the current index.
If they do not match, move to the next element.
Repeat this process until the end of the array.

\n\n

\n If the target is not found after checking all elements, return -1.\n

\n\n

"},{"@context":"https://schema.org","@type":"SoftwareSourceCode","programmingLanguage":"java","codeSampleType":"starter","text":"public static class Solution {\n /**\n * This method searches for a target value in a rotated sorted array.\n * It should return the index of the target if found, otherwise -1.\n *\n * @param nums The rotated sorted array.\n * @param target The value to search for.\n * @return The index of the target if found, otherwise -1.\n */\n public int search(int[] nums, int target) {\n // TODO: Implement the search algorithm\n return -1;\n }\n}\n","description":"Search in Rotated Sorted Array implementation in java"},{"@context":"https://schema.org","@type":"SoftwareSourceCode","programmingLanguage":"cpp","codeSampleType":"optimize","text":"class Solution {\npublic:\n int search(vector& nums, int target) {\n // Initialize left and right pointers for binary search.\n int left = 0, right = nums.size() - 1;\n \n // Continue binary search while the left pointer is less than or equal to the right pointer.\n while (left <= right) {\n // Calculate the middle index to avoid potential overflow.\n int mid = left + (right - left) / 2;\n \n // If the middle element is the target, return the index.\n if (nums[mid] == target) {\n return mid;\n }\n \n // Determine which half is sorted to decide where to search next.\n if (nums[left] <= nums[mid]) {\n // Left half is sorted.\n // If the target is within the sorted left half, search in the left half.\n if (nums[left] <= target && target < nums[mid]) {\n right = mid - 1;\n } else {\n // Otherwise, search in the right half.\n left = mid + 1;\n }\n } else {\n // Right half is sorted.\n // If the target is within the sorted right half, search in the right half.\n if (nums[mid] < target && target <= nums[right]) {\n left = mid + 1;\n } else {\n // Otherwise, search in the left half.\n right = mid - 1;\n }\n }\n }\n \n // If the target is not found, return -1.\n return -1;\n }\n};","description":"

\n\n

\n This allows us to search efficiently without scanning every element, even\n though the array is not fully sorted.\n

\n\n

\n Step-by-step thinking:\n

\n\n

Initialize two pointers: left at the start and right at the end of the array.
While left is less than or equal to right:

Compute the middle index mid.
If nums[mid] equals the target, return mid.
Check which half of the array is sorted.
If the left half is sorted, verify whether the target lies within it.
If it does, move right to mid - 1; otherwise move left to mid + 1.
If the right half is sorted, verify whether the target lies within it.
If it does, move left to mid + 1; otherwise move right to mid - 1.

If the loop ends without finding the target, return -1.

\n\n

\n Time Complexity: O(log n)
\n Space Complexity: O(1)
\n

\n"},{"@context":"https://schema.org","@type":"SoftwareSourceCode","programmingLanguage":"cpp","codeSampleType":"brute-force","text":"class Solution {\npublic:\n int search(vector& nums, int target) {\n\n // Loop through every element in the array\n for (int i = 0; i < nums.size(); i++) {\n\n // If current element matches target\n if (nums[i] == target) {\n return i; // return index\n }\n }\n\n // Target not found\n return -1;\n }\n};\n","description":"

\n\n

\n This approach is similar to searching for a word in a book by reading each\n page sequentially until you find the correct one.\n

\n\n

\n Step-by-step thinking:\n

\n\n

Start from the first element of the array.
Compare the current element with the target value.
If they match, return the current index.
If they do not match, move to the next element.
Repeat this process until the end of the array.

\n\n

\n If the target is not found after checking all elements, return -1.\n

\n\n

"},{"@context":"https://schema.org","@type":"SoftwareSourceCode","programmingLanguage":"cpp","codeSampleType":"starter","text":"class Solution {\npublic:\n /**\n * This function searches for a target value in a rotated sorted array.\n * @param nums The rotated sorted array to search in.\n * @param target The value to search for.\n * @return The index of the target if found, otherwise -1.\n */\n int search(vector& nums, int target) {\n // TODO: Implement the search algorithm here.\n // The array is rotated, so a standard binary search won't work directly.\n // You'll need to handle the rotation.\n return -1;\n }\n};\n","description":"Search in Rotated Sorted Array implementation in cpp"},{"@context":"https://schema.org","@type":"SoftwareSourceCode","programmingLanguage":"TypeScript","codeSampleType":"optimize","text":"function search(nums: number[], target: number): number {\n // Initialize the left and right pointers for binary search.\n let left = 0, right = nums.length - 1;\n \n // Continue binary search while the left pointer is less than or equal to the right pointer.\n while (left <= right) {\n // Calculate the middle index.\n const mid = Math.floor((left + right) / 2);\n \n // If the middle element is the target, return the middle index.\n if (nums[mid] === target) {\n return mid;\n }\n \n // Determine which half is sorted.\n if (nums[left] <= nums[mid]) {\n // Left half is sorted.\n // If the target is within the sorted left half.\n if (nums[left] <= target && target < nums[mid]) {\n // Adjust the right pointer to search in the left half.\n right = mid - 1;\n } else {\n // Otherwise, the target is in the right half (or not present).\n // Adjust the left pointer to search in the right half.\n left = mid + 1;\n }\n } else {\n // Right half is sorted.\n // If the target is within the sorted right half.\n if (nums[mid] < target && target <= nums[right]) {\n // Adjust the left pointer to search in the right half.\n left = mid + 1;\n } else {\n // Otherwise, the target is in the left half (or not present).\n // Adjust the right pointer to search in the left half.\n right = mid - 1;\n }\n }\n }\n \n // If the target is not found, return -1.\n return -1;\n}","description":"Search in Rotated Sorted Array implementation in TypeScript"},{"@context":"https://schema.org","@type":"SoftwareSourceCode","programmingLanguage":"TypeScript","codeSampleType":"brute-force","text":"function search(nums: number[], target: number): number {\n // Loop through every element in the array\n for (let i = 0; i < nums.length; i++) {\n // If current element matches target\n if (nums[i] === target) {\n return i; // return index\n }\n }\n\n // Target not found\n return -1;\n}","description":"Search in Rotated Sorted Array implementation in TypeScript"},{"@context":"https://schema.org","@type":"SoftwareSourceCode","programmingLanguage":"TypeScript","codeSampleType":"starter","text":"\nfunction search(nums: number[], target: number): number {\n // TODO: Implement the search function\n // Use binary search to find the target in the rotated sorted array.\n // Consider the cases where the left or right half is sorted.\n\n return -1; // Placeholder return value\n}\n","description":"Search in Rotated Sorted Array implementation in TypeScript"}]}

75. Search in Rotated Sorted Array

Understand Before Coding

Visualize This Problem

Draw Your Approach

Example 1:

Example 2:

Example 3:

Constraints:

Learn

Topics

Companies

Hint

Use Cases

75. Search in Rotated Sorted Array

Understand Before Coding

Visualize This Problem

Draw Your Approach

Example 1:

Example 2:

Example 3:

Constraints:

Learn

Topics

Companies

Hint

Use Cases