{"id":"874e0dbc-8f1d-48f2-8d0c-f5010c327058","name":"Search In Rotated Sorted Array","description":"1. There is an integer array nums sorted in ascending order (with distinct values).\r\n2. 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].\r\n3. 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.\r\n4. You must write an algorithm with O(log n) runtime complexity.","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"1 &lt;= nums.length &lt;= 5000\r\n-10^4 &lt;= nums[i] &lt;= 10^4\r\nAll values of nums are unique.\r\nnums is guaranteed to be rotated at some pivot.\r\n-10^4 &lt;= target &lt;= 10^4","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nint solution(vector<int> & arr, int target){\n // Write your code here\n}\n\nint main(){\n int n;\n cin>>n;\n vector<int> arr(n,0);\n for(int i=0; i<n; i++){\n cin>>arr[i];\n }\n int tar;\n cin>>tar;\n int ans = solution(arr,tar);\n cout<<ans<<endl;\n}"},"java":{"code":"import java.util.*;\r\nimport java.io.*;\r\n\r\npublic class Main {\r\n\r\n public static int find(int[]arr,int target) {\r\n //write your code here\r\n }\r\n\r\n public static void main(String[]args) {\r\n //input work\r\n Scanner scn = new Scanner(System.in);\r\n int n = scn.nextInt();\r\n int[]arr = new int[n];\r\n\r\n for(int i=0; i < n;i++) {\r\n arr[i] = scn.nextInt();\r\n }\r\n\r\n int target = scn.nextInt();\r\n int ans = find(arr,target);\r\n System.out.println(ans);\r\n }\r\n}"},"python":{"code":"def main():\r\n pass\r\nif_name_=='__main__':\r\n main()"}},"points":10,"difficulty":"medium","sampleInput":"7\r\n4 5 6 7 0 1 2\r\n1","sampleOutput":"5","questionVideo":"https://www.youtube.com/embed/1uu3g_uu8O0","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"cb36811c-9cd7-4d80-aa52-ae9b8409862a","name":"Searching And Sorting For Intermediate","slug":"searching-and-sorting-for-intermediate-10001","type":0},{"id":"97a1ab06-8552-47ee-a342-b5d04db96f84","name":"Search In Rotated Sorted Array","slug":"search-in-rotated-sorted-array","type":1}],"next":{"id":"a3c187b3-8c31-4ec2-86bd-b35a7191ace3","name":"Search in rotated sorted array","type":3,"slug":"search-in-rotated-sorted-array"},"prev":{"id":"4cb02e5a-26be-4bb0-b498-1e43975a02c8","name":"Find K Closest Elements Medium MCQ","type":0,"slug":"find-k-closest-elements-medium-mcq"}}}

Search In Rotated Sorted Array

1. There is an integer array nums sorted in ascending order (with distinct values). 2. 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]. 3. 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. 4. You must write an algorithm with O(log n) runtime complexity.

{"id":"874e0dbc-8f1d-48f2-8d0c-f5010c327058","name":"Search In Rotated Sorted Array","description":"1. There is an integer array nums sorted in ascending order (with distinct values).\r\n2. 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].\r\n3. 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.\r\n4. You must write an algorithm with O(log n) runtime complexity.","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"1 &lt;= nums.length &lt;= 5000\r\n-10^4 &lt;= nums[i] &lt;= 10^4\r\nAll values of nums are unique.\r\nnums is guaranteed to be rotated at some pivot.\r\n-10^4 &lt;= target &lt;= 10^4","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nint solution(vector<int> & arr, int target){\n // Write your code here\n}\n\nint main(){\n int n;\n cin>>n;\n vector<int> arr(n,0);\n for(int i=0; i<n; i++){\n cin>>arr[i];\n }\n int tar;\n cin>>tar;\n int ans = solution(arr,tar);\n cout<<ans<<endl;\n}"},"java":{"code":"import java.util.*;\r\nimport java.io.*;\r\n\r\npublic class Main {\r\n\r\n public static int find(int[]arr,int target) {\r\n //write your code here\r\n }\r\n\r\n public static void main(String[]args) {\r\n //input work\r\n Scanner scn = new Scanner(System.in);\r\n int n = scn.nextInt();\r\n int[]arr = new int[n];\r\n\r\n for(int i=0; i < n;i++) {\r\n arr[i] = scn.nextInt();\r\n }\r\n\r\n int target = scn.nextInt();\r\n int ans = find(arr,target);\r\n System.out.println(ans);\r\n }\r\n}"},"python":{"code":"def main():\r\n pass\r\nif_name_=='__main__':\r\n main()"}},"points":10,"difficulty":"medium","sampleInput":"7\r\n4 5 6 7 0 1 2\r\n1","sampleOutput":"5","questionVideo":"https://www.youtube.com/embed/1uu3g_uu8O0","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"cb36811c-9cd7-4d80-aa52-ae9b8409862a","name":"Searching And Sorting For Intermediate","slug":"searching-and-sorting-for-intermediate-10001","type":0},{"id":"97a1ab06-8552-47ee-a342-b5d04db96f84","name":"Search In Rotated Sorted Array","slug":"search-in-rotated-sorted-array","type":1}],"next":{"id":"a3c187b3-8c31-4ec2-86bd-b35a7191ace3","name":"Search in rotated sorted array","type":3,"slug":"search-in-rotated-sorted-array"},"prev":{"id":"4cb02e5a-26be-4bb0-b498-1e43975a02c8","name":"Find K Closest Elements Medium MCQ","type":0,"slug":"find-k-closest-elements-medium-mcq"}}}
plane

Editor


Loading...

Search In Rotated Sorted Array

medium

1. There is an integer array nums sorted in ascending order (with distinct values). 2. nums is rotated at an unknown pivot index k (0

Constraints

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

Format

Input

Input is managed for you

Output

Output is managed for you

Example

Sample Input

7 4 5 6 7 0 1 2 1

Sample Output

5

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode