33 & 81 Search in Rotated Sorted Array

Search in Rotated Sorted Array I

Problem Statement

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

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. (link)

Example 1

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

Optimal Approach

We will use a binary search approach.

The core idea is the midpoint divides the array into 2 halves only one part is sorted.

Elimination is a key factor in binary search. Knowing which half to eliminate is crucial. The main objective is to identify which half is sorted. We check if the target value is in the sorted half; if it is, we explore that half further. Otherwise, we check the unsorted half. To determine which half is sorted, we compare the mid-value with the left end. If the sorted array is on the left, we concentrate on the left part; otherwise, it is evident that the right half is sorted.

Code

class Solution {

    public int search(int[] nums, int target) {

        int low = 0;
        int high = nums.length - 1;

        while(low<=high){
            int mid = (low+high)>>1;
            if(nums[mid]==target) return mid;

            if(nums[low]<=nums[mid]){
                if(nums[low]<=target && target <= nums[mid]){
                    high = mid-1;
                } else{
                    low = mid+1;
                }
            } else{
                if(nums[mid]<=target && target<=nums[high]){
                    low = mid+1;
                }else {
                    high = mid-1;
                }
            }
        }
        return -1;
    }
}

Search in Rotated Sorted Array II

Problem Statement

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

Optimal Approach

The solution is the same as the rotated sorted array 1 problem. The only thing is if there are duplicates then identifying which part of the array is sorted is difficult.

Example 1

Example 2

Code

class Solution {

    public boolean search(int[] nums, int target) {
        int low = 0;
        int high = nums.length-1;

        while(low<=high){
            int mid = (low+high)>>1;

            if(nums[mid]==target) return true;

            if(nums[low]==nums[mid] && nums[mid]==nums[high]){
                low = low+1;
                high = high-1;
                continue;
            }

            if(nums[low]<=nums[mid]){
                if(nums[low]<=target && target<=nums[mid]){
                    high = mid-1;
                } else{
                    low = mid+1;
                }
            } else{
                if(nums[mid]<=target && target<=nums[high]){
                    low = mid+1;
                } else{
                    high = mid-1;
                }
            }
        }
        return false;
    }
}