Search a Rotated Sorted Array in One Binary-Search Pass

Question

The question asks the candidate to implement a binary search algorithm to find a target value in a rotated sorted array in a single pass.

Codemia · Accepted Answer

To search for a target value in a rotated sorted array, we can leverage the properties of binary search. The key idea is to determine which part of the array is sorted and then decide which side to search based on the target's value.

Here is a Python implementation of the binary search for a rotated sorted array:

```python
def search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        # Determine which side is sorted
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1
```
This code efficiently finds the target in a rotated sorted array.

The time complexity of this binary search algorithm is O(log n) because we are halving the search space with each iteration. The space complexity is O(1) since we are using a constant amount of space.

It is important to handle edge cases such as an empty array, where the function should return -1 immediately. Additionally, if the target is not present in the array, the function should also return -1.

Interviewers are looking for clarity in your explanation and your ability to articulate the thought process behind your solution. They also want to see if you can handle edge cases and discuss the efficiency of your algorithm.

Search a Rotated Sorted Array in One Binary-Search Pass

eBay

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

eBay Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string