சுழற்ற வரிசைப்படுத்தப்பட்ட வரிசை லீட்கோட் தீர்வில் தேடுங்கள்


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது அடோப் அலிபாபா அமேசான் ஆப்பிள் ப்ளூம்பெர்க் ByteDance சிஸ்கோ ஈபே Expedia பேஸ்புக் கோல்ட்மேன் சாக்ஸ் கூகிள் ஜேபி மோர்கன் லின்க்டு இன் மைக்ரோசாப்ட் Nutanix என்விடியா ஆரக்கிள் பேபால் Paytm விற்பனைக்குழு சாம்சங் ServiceNow பராமரிப்பு Tencent டெஸ்லா நிலையங்கள் டிவிச் கிழித்து நிகழ்ச்சி , VMware வால்மார்ட் ஆய்வகங்கள் யாகூ யாண்டேக்ஸ் 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

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (என்), ஏனெனில் மிக மோசமான நிலையில், வரிசையின் முடிவில் இலக்கு உறுப்பு இருக்கலாம். இதனால் நேர சிக்கலானது நேரியல்.

விண்வெளி சிக்கலானது

ஓ (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), சில நிலையான எண்ணிக்கையிலான உறுப்புகளை மட்டுமே நாங்கள் சேமித்து வைத்திருப்பதால், இட சிக்கலானது நிலையானது.