LeetCode - Search in Rotated Sorted Array - The Coding Shala

Home >> Interview Questions >> search in rotated sorted array

LeetCode - Search in Rotated Sorted Array

In this post, you will learn how to search an element in a rotated sorted array and returns its index. We will use the binary search algorithm here.

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). You are given a target value to search. If found in the array return its index, otherwise return -1. 

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

Search in Rotated Sorted Array Java

We can search in the array using the loop and return if the target is found or not but this would take O(n) time. this is not a good idea here. Instead of using normal search we will use Binary Search Algorithm.
Java Program: 

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        while(left<=right){
            int mid = left+(right-left)/2;
            //check for mid
            if(nums[mid]==target) return mid;
            //check if first half is in order
            if(nums[left]<=nums[mid]){
                //check if target is in first half or not
                if(target>=nums[left] && target<nums[mid]) right = mid-1;
                else left = mid+1;
            }
            //second half is in order
            else{
                //target is in second half or not
                if(target>nums[mid] && target<=nums[right]) left = mid+1;
                else right = mid-1;
            }
        }
        return -1;
    }
}


Other Posts You May Like
Please leave a comment below if you like this post or found some error, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Java Program to Convert Binary to Decimal - The Coding Shala

N-th Tribonacci Number Solution - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

InterviewBit - Colorful Number Solution - The Coding Shala