### LeetCode - Search in Rotated Sorted Array - The Coding Shala

Home >> Interview Questions >> search in rotated sorted array

## LeetCode - Search in Rotated Sorted Array

In this post, you will learn how to search an element in a rotated sorted array and returns its index. We will use the binary search algorithm here.

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). You are given a target value to search. If found in the array return its index, otherwise return -1.

Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

## Search in Rotated Sorted Array Java

We can search in the array using the loop and return if the target is found or not but this would take O(n) time. this is not a good idea here. Instead of using normal search we will use Binary Search Algorithm.
Java Program:

```class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length-1;
while(left<=right){
int mid = left+(right-left)/2;
//check for mid
if(nums[mid]==target) return mid;
//check if first half is in order
if(nums[left]<=nums[mid]){
//check if target is in first half or not
if(target>=nums[left] && target<nums[mid]) right = mid-1;
else left = mid+1;
}
//second half is in order
else{
//target is in second half or not
if(target>nums[mid] && target<=nums[right]) left = mid+1;
else right = mid-1;
}
}
return -1;
}
}
```

Other Posts You May Like