 Register for our webinar

### How to Nail your next Technical Interview

1 hour 1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name  Step 1  Step 2
Congratulations!
You have registered for our webinar Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone  Step 1  Step 2 Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.  ## You may be missing out on a 66.5% salary hike* ### Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students Help us know you better!

## How many years of coding experience do you have?

Oops! Something went wrong while submitting the form.  ## FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Oops! Something went wrong while submitting the form.  ### Attend our Free Webinar on How to Nail Your Next Technical Interview

WEBINAR +LIVE Q&A

## How To Nail Your Next Tech Interview Hosted By
Ryan Valles
Founder, Interview Kickstart Our tried & tested strategy for cracking interviews How FAANG hiring process works The 4 areas you must prepare for How you can accelerate your learnings

# Searching an Element in a Sorted and Rotated Array: Single-pass Binary Search Using Casework

For software engineers, preparing for a tech interview means a lot of practice! Not only must you practice several problems, but you also need to ensure that you cover a wide variety of topics.

In this article, we’re going to tackle a problem on search, which will, in turn, help you crack a number of complex problems — searching an element in a sorted and rotated array.

We solve it using “single-pass binary search using casework.” This is approach 3 of 4.

Here, we cover:

• Problem statement
• Approach explanation
• Algorithm for the approach
• Code for the approach
• Time complexity of the approach
• Space complexity of the approach

## Problem Statement

You have been given a sorted and rotated array "arr" of "N" distinct integers. You are also given an integer "target." Your task is to print the index of the integer "target" in array "arr." If "target" does not exist in "arr," then you need to print -1.

Note:

• "arr" contains distinct elements. This means that there is NO pair of indices (i, j) such that 0 <= i < j < N and arr[i] equals arr[j].
• "arr" is a rotated sorted array.

The following array adheres to all the above conditions:

Now, if we rotate it three times towards the right, we get a sorted and rotated array:

Let’s take a couple of input examples:

Input 1: arr = [9, 11, 1, 3, 5 ,7] and target = 5
Output 1: 4
Explanation 1: 5 is present at index 4, so we need to print 4.

Input 2: arr = [9, 11, 1, 3, 5 ,7] and target = 8
Output 2: -1
Explanation 2: 8 is not present in "arr," so we need to print -1.

Now that we have a clear understanding of our problem, we will move to the solution.

Please make sure you’ve read Approach 1 and Approach 2 to understand the coverage better.

## Approach 3: Single-pass Binary Search Using Casework

Key observation: If you divide the given array into two parts, there will be at least one part sorted in increasing order. So, we just need to do some casework to move our left and right pointers which are the two endpoints of our search space. How will we do this? Let’s take an example:

This is the array:

And this the target: 8

Step 1: Initialize left = 0 and right = 7
Calculate mid as mid = (left + right)/2 = 3

Here, we can see that arr[left] <= arr[mid]. So, arr[left...mid] must be sorted. We can now check if the target lies between [left, mid]. If not, we need to move left to mid + 1 as the target does not exist in [left, mid].

target >= arr[left] and target < arr[mid], i.e., target = 8 lies in [left, mid).

So, we will move left and set right to right = mid - 1 = 2.

Step 2: Left = 0 and right = 2
mid = (left + right)/2 = 1

Here, arr[left] <= arr[mid]. So, arr[left ... mid] is sorted. Now, we check if the target lies in arr[left, mid) = . But the target does not lie in this range. So, set left = mid + 1 = 2

Step 3: Left = 2 and right = 2
mid = (left + right)/2 = 2

Here. arr[mid] is equal to target. We’ve found our target, and we return it.

### Algorithm

1. Declare three variables "left", "right," and "mid" for binary search, and initialize left = 0, right = size of array - 1.

2. Run a loop until left <= right (standard binary search).

a. Calculate mid as mid = (left + right)/2.

b. If arr[mid] == target, then return mid as we have found our required element.

c. If arr[left] <=arr[mid], then do:

i. If target >= arr[left] and target < arr[mid], then search in [left, mid) and set right := mid - 1.

ii. Else, search in (mid, right] and set left = mid + 1.

d. If arr[mid] <= arr[right], then do:

i. If target > arr[mid] and target <= arr[right], then search in (mid, right] and set left := mid + 1.

ii. Else, search in [left, mid) and set right := mid - 1.

3. Return -1 as we are not able to find the target in our array "arr."

## Code in C++

We’ve implemented the algorithm in C++. Use this as a reference to code in a programming language of your choice.

/*
Time Complexity:  O(log(N))
Space Complexity: O(1)

Where N is the total number of elements in the given array.
*/

#include<iostream>
using namespace std;

// Function to search target in array 'arr'
int searchInRotatedSortedArray(int arr[], int n, int target)
{
int left = 0, right = n - 1, mid;

while (left <= right)
{
int mid = (left + right) / 2;
// We have found our target
if (arr[mid] == target)
{
return mid;
}

// Check if arr[left . . . mid] is sorted
if (arr[left] <= arr[mid])
{
// If target lies in arr[left, mid)
if (target >= arr[left] and target < arr[mid])
{
right = mid - 1;
}
else
{
left = mid + 1;
}
}

// Check if arr[mid . . . right] is sorted
if (arr[mid] <= arr[right])
{
// If target lies in arr(mid, right]
if (target > arr[mid] and target <= arr[right])
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
}

// We are not able to find target in array so return -1
return -1;
}

int main()
{

int n = 10;

int arr[n] = {10, 13, 16, 20, 25, 1, 3, 4, 5, 8};

int target = 4;

cout << searchInRotatedSortedArray(arr, n, target);

return 0;
}

## Time Complexity

O(log(N)), where "N" is the total number of elements in the given array.

We are reducing our search space by half at each step. So, we will get a recurrence as T(N) = T(N / 2) + C, where C is constant. Look at the previous approach for its proof.

Best Case: O(1)
Happens when arr[mid] equals to target for the first value of mid

Worst Case: O(log(N))
Happens when the target is not present in the array

Average case: O(log(N))
Happens when the target is present in the array. We need to do log(N) steps on average to search for a target.

## Space Complexity

Best Case = Worst Case = Average Case = O(1)

We are using a few extra variables that take O(1) space. Hence, the space complexity will be O(1).

## There’s More ...

While this approach works better than using linear search and two-pass binary search, there’s yet another approach that employs single-pass binary search by comparing mid and target elements. Read this article to learn more:

Searching an Element in a Sorted and Rotated Array: Single-pass Binary Search by Comparing Mid and Target Elements

As pioneers in the field of technical interview prep, we have trained over 5200 software engineers to crack the toughest coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!

————

Article contributed by Pankaj Sharma

Last updated on:
September 29, 2023 Engineering Manager at Interview Kickstart

# Searching an Element in a Sorted and Rotated Array: Single-pass Binary Search Using Casework

## Worried About Failing Tech Interviews?

Attend our webinar on
"How to nail your next tech interview" and learn Hosted By
Ryan Valles
Founder, Interview Kickstart Our tried & tested strategy for cracking interviews How FAANG hiring process works The 4 areas you must prepare for How you can accelerate your learnings