# 1. Introduction

This blog post focuses on solving a unique problem in array manipulation: searching for a target value in a rotated sorted array. In this scenario, a sorted array is rotated at some unknown pivot, and the challenge is to efficiently find a target value in this modified array using an approach with O(log n) runtime complexity.

## Problem

Given a rotated sorted array and a target value, find the index of the target if it's present in the array, otherwise return -1.

Example 1:

Input: nums = [8, 11, 13, 15, 1, 4, 6], target = 1

Output: 4

Example 2:

Input: nums = [1, 4, 6, 8, 11, 13, 15], target = 3

Output: -1

# 2. Solution Steps

1. Apply binary search to find the pivot point where the array is rotated.

2. Once the pivot is found, perform a binary search in the appropriate half of the array where the target is likely to be found.

3. If the target is found, return its index; otherwise, return -1.

# 3. Code Program

``````public class Solution {

// Main method for testing
public static void main(String[] args) {
int[] nums1 = {8, 11, 13, 15, 1, 4, 6};
System.out.println("Index of 1: " + search(nums1, 1));

int[] nums2 = {1, 4, 6, 8, 11, 13, 15};
System.out.println("Index of 3: " + search(nums2, 3));
}

// Method to search in a rotated sorted array
public static int search(int[] nums, int target) {
int start = 0, end = nums.length - 1;

while (start <= end) {
int mid = start + (end - start) / 2;

if (nums[mid] == target) {
return mid;
}

// Check if left half is sorted
if (nums[start] <= nums[mid]) {
if (target >= nums[start] && target < nums[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
// Right half is sorted
else {
if (target > nums[mid] && target <= nums[end]) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
}
}
``````

### Output:

```Index of 1: 4
Index of 3: -1
```

### Explanation:

The search method applies a modified binary search to efficiently find the target in a rotated sorted array. It first identifies which half of the array is sorted and then decides the search range accordingly.

For instance, in the array [8, 11, 13, 15, 1, 4, 6] with target 1, the method correctly identifies the sorted part of the array and finds 1 at index 4.

For the second example, the target 3 is not found in the array, resulting in -1.