## C# || How To Search In Rotated Sorted Array Using C#

The following is a module with functions which demonstrates how to search for a target value in a rotated sorted array using C#.

1. Search – Problem Statement

There is an integer array **nums** sorted in ascending order (with **distinct** values).

Prior 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]**.

Given 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**.

You must write an algorithm with **O(log n)** runtime complexity.

**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

**Example 3:**

Input: nums = [1], target = 0

Output: -1

2. Search – Solution

The following is a solution which demonstrates how to search for a target value in a rotated sorted array.

The idea of this solution is to use binary search, and for each loop iteration we compare the midpoint element with the right side of the array to determine the search area of where the target element might be.

```
```
1234567891011121314151617181920212223242526272829303132333435363738394041
// ============================================================================// Author: Kenneth Perkins// Date: Nov 26, 2021// Taken From: http://programmingnotes.org/// File: Solution.cs// Description: Demonstrates how to search for a target in a rotated array// ============================================================================public class Solution { public int Search(int[] nums, int target) { var lo = 0; var hi = nums.Length - 1; while (lo <= hi) { var mid = lo + (hi - lo) / 2; // Target element found if (nums[mid] == target) { return mid; // Midpoint element is greater than right side of array } else if (nums[mid] > nums[hi]) { // Determine which side of array to adjust if (target < nums[mid] && target >= nums[lo]) { hi = mid - 1; } else { lo = mid + 1; } // Midpoint element is less than right side of array } else { // Determine which side of array to adjust if (target > nums[mid] && target <= nums[hi]) { lo = mid + 1; } else { hi = mid - 1; } } } return -1; }}// http://programmingnotes.org/

**QUICK NOTES**:

The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

4

-1

-1

## Leave a Reply