ঘোরানো সাজানো অ্যারে লেটকোড সলিউশন অনুসন্ধান করুন


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় রৌদ্রপক্ব ইষ্টক আলিবাবা মর্দানী স্ত্রীলোক আপেল ব্লুমবার্গ ByteDance সিসকো ইবে এক্সপিডিয়া ফেসবুক গোল্ডম্যান শ্যাস গুগল জে পি মরগ্যান লিঙ্কডইন মাইক্রোসফট Nutanix এনভিডিয়া আকাশবাণী পেপ্যাল Paytm বিক্রয় বল স্যামসাং ServiceNow টেন সেন্ট টেসলা দাবি পিটপিট্ উবার ভিসা কার্ড অথবা VMware ওয়ালমার্ট ল্যাব নরপশু ইয়ানডেক্স Zillow জুলিলি
বিন্যাস বাইনারি অনুসন্ধান

বাছাই করা অ্যারে বিবেচনা করুন তবে একটি সূচক বাছাই করা হয়েছিল এবং অ্যারেটি সেই সময়ে ঘোরানো হয়েছিল। এখন একবার অ্যারে ঘোরানো হলে আপনাকে একটি নির্দিষ্ট লক্ষ্য উপাদান খুঁজে বের করতে হবে এবং এর সূচকটি ফেরত দিতে হবে। ক্ষেত্রে, উপাদান উপস্থিত নেই, ফিরে -1। সমস্যাটি সাধারণত সন্ধান ইন আবর্তিত সাজানো অ্যারে লেটকোড সলিউশন হিসাবে উল্লেখ করা হয়। সুতরাং প্রশ্নে, আমাদের কিছু পরিসংখ্যক উপাদানগুলির একটি অ্যারে সরবরাহ করা হয় যা নির্দিষ্ট সূচীতে সাজানো এবং ঘোরানো হয় যা আমাদের জানা নেই। অ্যারের পাশাপাশি, আমাদের একটি সুনির্দিষ্ট উপাদানও দেওয়া হয়েছে যা আমাদের সন্ধান করা দরকার।

ঘোরানো সাজানো অ্যারে লেটকোড সলিউশন অনুসন্ধান করুন

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

ব্যাখ্যা: যেহেতু অনুসন্ধানের উপাদানটি 4 হয় The উপাদানটি সূচক 0-এ পাওয়া যায়, তাই আমরা লক্ষ্য সূচকে ফিরে আসি।

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

ব্যাখ্যা: উপাদান অ্যারে উপস্থিত না থাকায় আমরা -1 এ ফিরে আসি return

ঘোরানো সাজানো অ্যারে অনুসন্ধানের জন্য ব্রুট ফোর্স পদ্ধতির ach

সমস্যাটি "ঘোরানো সাজানো অ্যারেগুলিতে অনুসন্ধান" প্রদত্ত ঘোরানো বাছাই করা অ্যারেতে লক্ষ্য উপাদানটির সূচকটি খুঁজতে আমাদেরকে জিজ্ঞাসা করে। এবং আমরা ইতিমধ্যে আলোচনা করেছি যে একটি ঘোরানো সাজানো অ্যারে কী? সুতরাং, সবচেয়ে সহজ পদ্ধতি যার মধ্যে কেউ ভাবতে পারে তা হল লিনিয়ার সন্ধানের চেষ্টা করা। লিনিয়ার অনুসন্ধানে, আমরা কেবলমাত্র প্রদত্তটিকে অতিক্রম করি বিন্যাস এবং বর্তমান উপাদানটি আমাদের লক্ষ্য উপাদান কিনা তা পরীক্ষা করে দেখুন। বর্তমান উপাদান যদি লক্ষ্য উপাদান হয় তবে আমরা বর্তমান সূচকটি ফিরিয়ে দিই অন্যথায় আমরা ফিরে আসি -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

জটিলতা বিশ্লেষণ

সময় জটিলতা

চালু), কারণ সবচেয়ে খারাপ ক্ষেত্রে, অ্যারের শেষে লক্ষ্য উপাদান উপস্থিত থাকতে পারে। সুতরাং সময় জটিলতা রৈখিক হয়।

স্পেস জটিলতা ity

ও (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

জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (লগ এন), যেহেতু আমরা লক্ষ্য উপাদানটি খুঁজতে বাইনারি অনুসন্ধান ব্যবহার করেছি। সময়ের জটিলতা লগারিদমিক।

স্পেস জটিলতা ity

ও (1), যেহেতু আমরা কেবলমাত্র কয়েকটি ধ্রুব উপাদান রেখেছি তাই স্থান জটিলতা ধ্রুবক।