రొటేటెడ్ సార్టెడ్ అర్రే లీట్‌కోడ్ సొల్యూషన్‌లో శోధించండి


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది Adobe ఆలీబాబా అమెజాన్ ఆపిల్ బ్లూమ్బెర్గ్ ByteDance సిస్కో eBay Expedia ద్వారా <span style="font-family: Mandali; ">ఫేస్‌బుక్ </span> గోల్డ్మన్ సాచ్స్ గూగుల్ JP మోర్గాన్ లింక్డ్ఇన్ మైక్రోసాఫ్ట్ నూటనిక్స్ విడియా ఒరాకిల్ పేపాల్ Paytm అమ్మకాల బలం శామ్సంగ్ ServiceNow టెన్సెంట్ టెస్లా ట్రిప్అడ్వైజర్ పట్టేయడం ఉబెర్ వీసా VMware వాల్‌మార్ట్ ల్యాబ్స్ యాహూ Yandex Zillow జూలీ
అర్రే బైనరీ శోధన

క్రమబద్ధీకరించబడిన శ్రేణిని పరిగణించండి కాని ఒక సూచిక ఎంచుకోబడింది మరియు ఆ సమయంలో శ్రేణి తిప్పబడింది. ఇప్పుడు, శ్రేణిని తిప్పిన తర్వాత మీరు ఒక నిర్దిష్ట లక్ష్య మూలకాన్ని కనుగొని దాని సూచికను తిరిగి ఇవ్వాలి. ఒకవేళ, మూలకం లేనట్లయితే, తిరిగి -1. సమస్యను సాధారణంగా సెర్చ్ ఇన్ రొటేటెడ్ సార్టెడ్ అర్రే లీట్‌కోడ్ సొల్యూషన్ అని పిలుస్తారు. కాబట్టి ప్రశ్నలో, మనకు తెలియని ఒక నిర్దిష్ట సూచిక వద్ద క్రమబద్ధీకరించబడిన మరియు తిప్పబడిన కొన్ని పూర్ణాంక మూలకాల శ్రేణి మాకు అందించబడుతుంది. శ్రేణితో పాటు, మనకు కనుగొనవలసిన ఒక నిర్దిష్ట మూలకం కూడా ఇవ్వబడుతుంది.

రొటేటెడ్ సార్టెడ్ అర్రే లీట్‌కోడ్ సొల్యూషన్‌లో శోధించండి

array: [4,5,6,7,0,1,2]
target: 4
0

వివరణ: శోధించవలసిన మూలకం 4. కాబట్టి మూలకం సూచిక 0 వద్ద కనుగొనబడింది, మేము లక్ష్యం యొక్క సూచికను తిరిగి ఇస్తాము.

array: [4,5,6,7,0,1,2]
target: 3
-1

వివరణ: శ్రేణిలో మూలకం లేనందున, మేము -1 తిరిగి ఇస్తాము.

తిప్పబడిన క్రమబద్ధీకరించిన శ్రేణిలో శోధించడానికి బ్రూట్ ఫోర్స్ అప్రోచ్

“రొటేటెడ్ సార్టెడ్ అర్రేలో శోధించండి” అనే సమస్య ఇచ్చిన తిప్పబడిన క్రమబద్ధీకరించిన శ్రేణిలో లక్ష్య మూలకం యొక్క సూచికను కనుగొనమని అడుగుతుంది. తిరిగిన క్రమబద్ధీకరించిన శ్రేణి ఏమిటో మేము ఇప్పటికే చర్చించాము? కాబట్టి, సరళ శోధనను ప్రయత్నించడం అనేది ఆలోచించగల సరళమైన పద్ధతి. లీనియర్ సెర్చ్‌లో, మేము ఇచ్చిన వాటిని దాటుతాము అమరిక మరియు ప్రస్తుత మూలకం మా లక్ష్య మూలకం కాదా అని తనిఖీ చేయండి. ప్రస్తుత మూలకం లక్ష్య మూలకం అయితే మేము ప్రస్తుత సూచికను తిరిగి ఇస్తాము, లేకపోతే -1. విధానం చాలా సులభం, కానీ శ్రేణి ఒకే సూచిక వద్ద క్రమబద్ధీకరించబడింది మరియు తిప్పబడుతుంది అనే వాస్తవాన్ని ఇది ఉపయోగించదు. ఈ విధానం సరళ సమయ సంక్లిష్టతను కలిగి ఉంది.

రొటేటెడ్ సార్టెడ్ అర్రే లీట్‌కోడ్ సొల్యూషన్‌లో శోధన కోసం కోడ్

సి ++ కోడ్

#include <bits/stdc++.h>
using namespace std;

int search(vector<int>& nums, int target) {
    int n = nums.size();
    for(int i=0;i<n;i++)
        if(nums[i] == target)
            return i;
    return -1;
}

int main(){
    vector<int> nums({4,5,6,7,0,1,2});
    cout<<search(nums, 4);
}
0

జావా కోడ్

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static int search(int[] nums, int target) {
        int n = nums.length;
        for(int i=0;i<n;i++)
            if(nums[i] == target)
                return i;
        return -1;
    }
    
    public static void main(String[] args){
    	int nums[] = {4,5,6,7,0,1,2};
    	System.out.println(search(nums, 4));
    }
}
0

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై), ఎందుకంటే చెత్త సందర్భంలో, శ్రేణి చివరిలో లక్ష్య మూలకం ఉండవచ్చు. అందువలన సమయం సంక్లిష్టత సరళంగా ఉంటుంది.

అంతరిక్ష సంక్లిష్టత

O (1), ప్రతి మూలకానికి సంబంధించి మాకు ప్రత్యేకంగా ఎటువంటి సమాచారం లేదు మరియు స్థిరమైన వేరియబుల్స్ సంఖ్యను ఉపయోగించాము. అందువలన స్థల సంక్లిష్టత స్థిరంగా ఉంటుంది.

తిప్పబడిన క్రమబద్ధీకరించిన శ్రేణిలో శోధన కోసం ఆప్టిమైజ్ చేసిన విధానం

ఇంతకుముందు పేర్కొన్న విధానం శ్రేణి తిప్పబడిన క్రమబద్ధీకరించబడిన శ్రేణి అనే వాస్తవాన్ని ఉపయోగించలేదు. కాబట్టి, ఈ విధానంలో, సమయ సంక్లిష్టతను తగ్గించడానికి మేము ఈ వాస్తవాన్ని ఉపయోగించడానికి ప్రయత్నిస్తాము. పరిగణించండి, మనకు క్రమబద్ధీకరించబడిన శ్రేణి ఉంటే, మేము కేవలం ఉపయోగించుకుంటాము బైనరీ శోధన ఒకవేళ ఇది కొంచెం గమ్మత్తైనది. ఇక్కడ కూడా మేము బైనరీ శోధనను ఉపయోగించాల్సి ఉంటుంది. మేము బైనరీ శోధనను ఉపయోగిస్తే, శ్రేణి యొక్క మధ్య మూలకం వద్ద ఉన్నప్పుడు శ్రేణిలోని ఏ భాగాన్ని ఎంచుకోవాలో తెలుసుకోవడం ఎలా? ఎందుకంటే మనం అసలు బైనరీ సెర్చ్ అల్గోరిథంను అనుసరించలేము ఎందుకంటే ఇది తిప్పబడిన క్రమబద్ధీకరించబడిన శ్రేణి. కాబట్టి, సాధారణ బైనరీ శోధనపై స్వల్ప మార్పు ఉంది.

కాబట్టి, సాధారణంగా బైనరీ శోధనలో, ప్రస్తుత మూలకం (మధ్య సూచిక వద్ద మూలకం) లక్ష్యానికి సమానంగా ఉందో లేదో తనిఖీ చేస్తాము, అప్పుడు మేము దాని సూచికను తిరిగి ఇస్తాము. ఈ దశ ఇక్కడ అలాగే ఉంది. అలా కాకుండా, అవి ఒకేలా ఉండకపోతే, పైవట్ కుడివైపు [ప్రస్తుత మూలకం లేదా ఎడమ వైపున ఉందో లేదో మేము తనిఖీ చేస్తాము. ఇది కుడి వైపున ఉంటే, లక్ష్యం తిప్పబడని సబ్‌రేలో ఉందో లేదో తనిఖీ చేస్తాము, అది మనం ఎక్కువ అప్‌డేట్ చేస్తే మనం తక్కువ అప్‌డేట్ చేస్తాము. అదేవిధంగా, పైవట్ ఎడమ వైపున ఉంటే, లక్ష్యం తిరిగే కాని సబ్‌రేలో ఉందో లేదో మళ్ళీ తనిఖీ చేస్తాము, మేము తక్కువని అప్‌డేట్ చేస్తాము, లేకపోతే మేము హైని అప్‌డేట్ చేస్తాము. చివరికి, మేము లూప్ నుండి బయటకు వస్తే, ఇచ్చిన శ్రేణిలో లక్ష్యం లేదని మేము ఖచ్చితంగా అనుకుంటున్నాము.

రొటేటెడ్ సార్టెడ్ అర్రే లీట్‌కోడ్ సొల్యూషన్‌లో శోధన కోసం ఆప్టిమైజ్ కోడ్

సి ++ కోడ్

#include <bits/stdc++.h>
using namespace std;

int search(vector<int>& nums, int target) {
    int n = nums.size();
    int low = 0, high = n-1;
    while(low<=high){
        int mid = (low+high)/2;
        // check if the current element is target
        if(nums[mid] == target)
            return mid;
        // if the starting index of the search space has smaller element than current element
        else if(nums[low]<=nums[mid]){
            // if target lies in non-rotated search space (or subarray)
            if(target >= nums[low] && target < nums[mid])
                high = mid - 1;
            else
                low = mid + 1;
        } else {
            // if target lies in non-rotated subarray
            if(target>nums[mid] && target<=nums[high])
                low = mid + 1;
            else
                high = mid - 1;
        }
    }
    // if you couldn't find the target element until now then it does not exists
    return -1;
}
int main(){
    vector<int> nums({4,5,6,7,0,1,2});
    cout<<search(nums, 4);
}
0

జావా కోడ్

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static int search(int[] nums, int target) {
        int n = nums.length;
        int low = 0, high = n-1;
        while(low<=high){
            int mid = (low+high)/2;
            // check if the current element is target
            if(nums[mid] == target)
                return mid;
            // if the starting index of the search space has smaller element than current element
            else if(nums[low]<=nums[mid]){
                // if target lies in non-rotated search space (or subarray)
                if(target >= nums[low] && target < nums[mid])
                    high = mid - 1;
                else
                    low = mid + 1;
            } else {
                // if target lies in non-rotated subarray
                if(target>nums[mid] && target<=nums[high])
                    low = mid + 1;
                else
                    high = mid - 1;
            }
        }
        // if you couldn't find the target element until now then it does not exists
        return -1;
    }
    
    public static void main(String[] args){
    	int nums[] = {4,5,6,7,0,1,2};
    	System.out.println(search(nums, 4));
    }
}
0

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

ఓ (లాగ్ ఎన్), లక్ష్య మూలకాన్ని కనుగొనడానికి మేము బైనరీ శోధనను ఉపయోగించాము కాబట్టి. సమయం సంక్లిష్టత లోగరిథమిక్.

అంతరిక్ష సంక్లిష్టత

ఓ (1), మేము కొన్ని స్థిరమైన మూలకాలను మాత్రమే నిల్వ చేసినందున, స్థల సంక్లిష్టత స్థిరంగా ఉంటుంది.