தேடல் செருக நிலை லீட்கோட் தீர்வு  


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அடோப் அமேசான் ஆப்பிள் ப்ளூம்பெர்க் கூகிள் மைக்ரோசாப்ட்
அணி பைனரி தேடல் குறியீட்டு பேட்டி நேர்காணல் தயாரிப்பு லீட்கோட் LeetCodeSolutions

இந்த சிக்கலில், எங்களுக்கு ஒரு வரிசைப்படுத்தப்பட்டுள்ளது வரிசை மற்றும் ஒரு இலக்கு முழு எண். அதன் தேடல் செருகும் நிலையை நாம் கண்டுபிடிக்க வேண்டும்.

  1. இலக்கு மதிப்பு வரிசையில் இருந்தால், அதன் குறியீட்டை திருப்பி விடுங்கள்.
  2. வரிசையைச் வரிசைப்படுத்த (குறையாத முறையில்) இலக்கைச் செருக வேண்டிய குறியீட்டைத் திருப்பி விடுங்கள்.

உதாரணமாக  

1 2 3 4 5 
Target = 3
2
1 3 5 7 9
Target = 8
4

விளக்கம்

செருகு நிலை லீட்கோட் தீர்வுகள்முள்

அணுகுமுறை (நேரியல் தேடல்)  

இலக்கு குறியீட்டை விட அதிகமாகவோ அல்லது சமமாகவோ இருக்கும் முதல் குறியீட்டைக் கண்டுபிடிக்க நாம் ஒரு வட்டத்தை இயக்கலாம். ஆதாரம்:

  • மதிப்பு சமமாக இருந்தால், இந்த குறியீடு தேவையான குறியீடாகும்.
  • இல்லையெனில், இந்த நிலையில் இலக்கு செருகப்பட்டிருக்கும்.

அல்காரிதம்

  1. முதல் குறியீட்டிலிருந்து வரிசையின் இறுதி வரை ஒரு சுழற்சியை இயக்கவும்
  2. If வரிசை [i] இலக்கு மதிப்பை மீறுகிறது அல்லது சமப்படுத்துகிறது, பின்னர் நான் திரும்பவும்
  3. திரும்ப n, வரிசை [குறியீட்டு]> = இலக்கு போன்ற குறியீட்டை நாங்கள் காணவில்லை என்பதால் இலக்கு இறுதியில் செருகப்பட வேண்டும்
  4. முடிவை அச்சிடுங்கள்

இலக்கு தேடல் செருகும் நிலையைக் கண்டறிய வழிமுறையை செயல்படுத்துதல்

சி ++ திட்டம்

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

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


int main()
{
    vector <int> a = {1 , 3 , 5 , 7 , 9};
    int target = 8;
    cout << searchInsert(a , target) << '\n';
}

ஜாவா திட்டம்

class search_insert_position
{
    static int searchInsert(int[] a , int target)
    {
        int n = a.length;
        for(int i = 0 ; i < n ; i++)
        {
            if(a[i] >= target)
                return i;
        }
        return n;
    }

    public static void main(String args[])
    {
        int a[] = {1 , 3 , 5 , 7 , 9} , target = 8;
        System.out.println(searchInsert(a , target));
    }
}
4

தேடலின் தேடல் செருகும் நிலையைக் கண்டுபிடிப்பதற்கான சிக்கலான பகுப்பாய்வு

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

ஓ (என்), அங்கு வரிசையின் N = அளவு. மோசமான நிலையில், நாம் சேர்க்க வேண்டும் இலக்கு வரிசையின் முடிவில்.

மேலும் காண்க
த்ரெஷோல்ட் லீட்கோட் தீர்வு கொடுக்கப்பட்ட மிகச்சிறிய வகுப்பியைக் கண்டறியவும்

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

ஓ (1). மாறிகளுக்கு நிலையான இடத்தைப் பயன்படுத்துகிறோம்.

அணுகுமுறை (பைனரி தேடல்)  

வரிசை வரிசைப்படுத்தப்பட்டுள்ளது. இதிலிருந்து நாம் செய்யக்கூடிய முதல் முடிவு: சில குறியீட்டில் மதிப்பு இருந்தால் idx இலக்கை விட குறைவாக உள்ளது, பின்னர் எஞ்சியிருக்கும் கூறுகளை சரிபார்க்க தேவையில்லை idx, அவை இன்னும் சிறியதாக இருக்கும். எனவே நாம் ஒரு பயன்படுத்தலாம் பைனரி தேடல் தேடல் செருகும் நிலையைக் கண்டுபிடிக்க.

அல்காரிதம்

  1. உருவாக்கவும் பைனரிசர்ச் () தேவையான குறியீட்டை வழங்கும் செயல்பாடு
  2. துவக்க பதில் = 0, இது தேவையான குறியீட்டை சேமிக்கும்
  3. இடது மற்றும் வலது வரம்புகளை என அமைக்கவும் மற்றும் என் - 1 முறையே, வரிசையின் N = அளவு
  4. வரை இடது <= வலது
    • இந்த வரம்புகளின் நடுத்தர குறியீட்டைக் கண்டறியவும் mid = left + right / 2
    • If ஒரு [நடுப்பகுதி] == இலக்கு, நடுப்பகுதியில் திரும்பவும்
    • மதிப்பு அதிகமாக இருந்தால், நாம் இடது பாதியைப் பயன்படுத்தி நகர்கிறோம் வலது = நடுப்பகுதி - 1 சேமிக்கவும் விடை = நடுப்பகுதி
    • இது எப்போது வழக்கை விட்டு விடுகிறது ஒரு [நடு] <இலக்கு, நாங்கள் சேமிக்கிறோம் விடை = நடுப்பகுதி + 1 பயன்படுத்தி வலது பாதிக்கு நகரவும் இடது = நடுப்பகுதி + 1
    • திரும்பவும்
  5. முடிவை அச்சிடுங்கள்

இலக்கு லீட்கோட் தீர்வின் தேடல் செருகும் நிலையைக் கண்டறிய வழிமுறையை செயல்படுத்துதல்

சி ++ திட்டம்

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

int binarySearch(vector <int> &a , int target)
{
    int l = 0 , r = (int)a.size() - 1 , mid , ans = -1;
    while(l <= r)
    {
        mid = l + (r - l) / 2;
        if(a[mid] == target)
            return mid;
        if(a[mid] < target)
        {
            l = mid + 1;
            ans = mid + 1;
        }
        else
        {
            ans = mid;
            r = mid - 1;
        }
    }
    return ans;
}

int searchInsert(vector<int>& a, int target)
{
    return binarySearch(a , target);
}

int main()
{
    vector <int> a = {1 , 3 , 5 , 7 , 9};
    int target = 8;
    cout << searchInsert(a , target) << '\n';
}

ஜாவா திட்டம்

class search_insert_position
{
    static int binarySearch(int[] a , int target)
    {
        int l = 0 , r = a.length - 1 , mid , ans = -1;
        while(l <= r)
        {
            mid = l + (r - l) / 2;
            if(a[mid] == target)
                return mid;
            if(a[mid] < target)
            {
                l = mid + 1;
                ans = mid + 1;
            }
            else
            {
                ans = mid;
                r = mid - 1;
            }
        }
        return ans;
    }

    static int searchInsert(int[] a , int target)
    {
        return binarySearch(a , target);
    }

    public static void main(String args[])
    {
        int a[] = {1 , 3 , 5 , 7 , 9} , target = 8;
        System.out.println(searchInsert(a , target));
    }
}
4

இலக்கு லீட்கோட் தீர்வின் தேடல் செருகு நிலையை கண்டுபிடிப்பதன் சிக்கலான பகுப்பாய்வு

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

ஓ (logN). மோசமான நிலையில், நாம் செய்ய முடியும் logN ஒப்பீடுகள்.

மேலும் காண்க
பைனரி மரம் லீட்கோட் தீர்வின் குறைந்தபட்ச ஆழம்

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

ஓ (1). மீண்டும், மாறிகளுக்கு நிலையான இடத்தைப் பயன்படுத்துகிறோம்.