ತಿರುಗಿದ ವಿಂಗಡಿಸಲಾದ ಅರೇ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ಹುಡುಕಿ  


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಡೋಬ್ ಅಲಿಬಾಬಾ ಅಮೆಜಾನ್ ಆಪಲ್ ಬ್ಲೂಮ್ಬರ್ಗ್ ಬೈಟ್ ಡೇನ್ಸ್ ಸಿಸ್ಕೋ ಇಬೇ Expedia ಫೇಸ್ಬುಕ್ ಗೋಲ್ಡ್ಮನ್ ಸ್ಯಾಚ್ಸ್ ಗೂಗಲ್ JP ಮೋರ್ಗಾನ್ ಸಂದೇಶ ಮೈಕ್ರೋಸಾಫ್ಟ್ ನುಟಾನಿಕ್ಸ್ ಎನ್ವಿಡಿಯಾ ಒರಾಕಲ್ ಪೇಪಾಲ್ ಪೇಟ್ಮ್ ಸೇಲ್ಸ್ಫೋರ್ಸ್ ಸ್ಯಾಮ್ಸಂಗ್ ಸೇವೆ ಈಗ ಟೆನ್ಸೆಂಟ್ನ ಟೆಸ್ಲಾ ಟ್ರಿಪ್ ಅಡ್ವೈಸರ್ ಸೆಳೆಯು ಉಬರ್ ವೀಸಾ ವರೆ ವಾಲ್ಮಾರ್ಟ್ ಲ್ಯಾಬ್ಸ್ ಯಾಹೂ ಯಾಂಡೆಕ್ಸ್ ಝಿಲೋ ಜುಲಿಲಿ
ಅಲ್ಗಾರಿದಮ್ಗಳು ಅರೇ ಬೈನರಿ ಹುಡುಕಾಟ ಕೋಡಿಂಗ್ ಸಂದರ್ಶನ ಸಂದರ್ಶನ ಪೂರ್ವಭಾವಿ ಲೀಟ್‌ಕೋಡ್ LeetCodeSolutions

ವಿಂಗಡಿಸಲಾದ ಶ್ರೇಣಿಯನ್ನು ಪರಿಗಣಿಸಿ ಆದರೆ ಒಂದು ಸೂಚಿಯನ್ನು ಆರಿಸಲಾಯಿತು ಮತ್ತು ಆ ಸಮಯದಲ್ಲಿ ರಚನೆಯನ್ನು ತಿರುಗಿಸಲಾಯಿತು. ಈಗ, ರಚನೆಯನ್ನು ತಿರುಗಿಸಿದ ನಂತರ ನೀವು ನಿರ್ದಿಷ್ಟ ಗುರಿ ಅಂಶವನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕು ಮತ್ತು ಅದರ ಸೂಚಿಯನ್ನು ಹಿಂತಿರುಗಿಸಬೇಕು. ಒಂದು ವೇಳೆ, ಅಂಶವು ಅಸ್ತಿತ್ವದಲ್ಲಿಲ್ಲ, ಹಿಂತಿರುಗಿ -1. ಸಮಸ್ಯೆಯನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಹುಡುಕಾಟದಲ್ಲಿ ತಿರುಗಿದ ವಿಂಗಡಿಸಲಾದ ಅರೇ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಆದ್ದರಿಂದ ಪ್ರಶ್ನೆಯಲ್ಲಿ, ನಮಗೆ ತಿಳಿದಿಲ್ಲದ ಒಂದು ನಿರ್ದಿಷ್ಟ ಸೂಚ್ಯಂಕದಲ್ಲಿ ವಿಂಗಡಿಸಲಾದ ಮತ್ತು ತಿರುಗಿಸುವ ಕೆಲವು ಪೂರ್ಣಾಂಕ ಅಂಶಗಳ ಒಂದು ಶ್ರೇಣಿಯನ್ನು ನಮಗೆ ಒದಗಿಸಲಾಗಿದೆ. ರಚನೆಯ ಜೊತೆಗೆ, ನಾವು ಕಂಡುಹಿಡಿಯಬೇಕಾದ ನಿರ್ದಿಷ್ಟ ಅಂಶವನ್ನೂ ಸಹ ನಮಗೆ ನೀಡಲಾಗಿದೆ.

ತಿರುಗಿದ ವಿಂಗಡಿಸಲಾದ ಅರೇ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ಹುಡುಕಿ

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

ವಿವರಣೆ: ಹುಡುಕಬೇಕಾದ ಅಂಶ 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);
}

ಜಾವಾ ಕೋಡ್

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));
    }
}

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್), ಏಕೆಂದರೆ ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ, ರಚನೆಯ ಕೊನೆಯಲ್ಲಿ ಗುರಿ ಅಂಶವು ಇರಬಹುದು. ಹೀಗಾಗಿ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ರೇಖೀಯವಾಗಿರುತ್ತದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (1), ಏಕೆಂದರೆ ನಾವು ಪ್ರತಿಯೊಂದು ಅಂಶದ ಬಗ್ಗೆ ನಿರ್ದಿಷ್ಟವಾಗಿ ಯಾವುದೇ ಮಾಹಿತಿಯನ್ನು ಹೊಂದಿಲ್ಲ ಮತ್ತು ಸ್ಥಿರ ಸಂಖ್ಯೆಯ ಅಸ್ಥಿರಗಳನ್ನು ಬಳಸಿದ್ದೇವೆ. ಹೀಗಾಗಿ ಜಾಗದ ಸಂಕೀರ್ಣತೆ ಸ್ಥಿರವಾಗಿರುತ್ತದೆ.

ತಿರುಗುವ ವಿಂಗಡಿಸಲಾದ ಅರೇನಲ್ಲಿ ಹುಡುಕಾಟಕ್ಕಾಗಿ ಆಪ್ಟಿಮೈಸ್ಡ್ ಅಪ್ರೋಚ್  

ಮೊದಲೇ ಹೇಳಿದ ವಿಧಾನವು ರಚನೆಯು ತಿರುಗುವ ವಿಂಗಡಿಸಲಾದ ರಚನೆಯಾಗಿದೆ ಎಂಬ ಅಂಶವನ್ನು ಬಳಸಲಿಲ್ಲ. ಆದ್ದರಿಂದ, ಈ ವಿಧಾನದಲ್ಲಿ, ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ಕಡಿಮೆ ಮಾಡಲು ನಾವು ಈ ಸಂಗತಿಯನ್ನು ಬಳಸಲು ಪ್ರಯತ್ನಿಸುತ್ತೇವೆ. ಪರಿಗಣಿಸಿ, ನಾವು ವಿಂಗಡಿಸಲಾದ ಶ್ರೇಣಿಯನ್ನು ಹೊಂದಿದ್ದರೆ, ನಾವು ಸರಳವಾಗಿ ಬಳಸುತ್ತಿದ್ದೆವು ಬೈನರಿ ಹುಡುಕಾಟ ಆದರೆ ಇದು ಸ್ವಲ್ಪ ಟ್ರಿಕಿ ಆಗಿದ್ದರೆ. ಇಲ್ಲಿ ನಾವು ಬೈನರಿ ಹುಡುಕಾಟವನ್ನು ಬಳಸಬೇಕಾಗುತ್ತದೆ. ಆದರೆ ನಾವು ಬೈನರಿ ಹುಡುಕಾಟವನ್ನು ಬಳಸಿದರೆ, ನಾವು ರಚನೆಯ ಮಧ್ಯದ ಅಂಶದಲ್ಲಿದ್ದಾಗ ಯಾವ ಶ್ರೇಣಿಯನ್ನು ಆರಿಸಬೇಕೆಂದು ನಾವು ಹೇಗೆ ತಿಳಿಯುತ್ತೇವೆ? ಏಕೆಂದರೆ ನಾವು ಮೂಲ ಬೈನರಿ ಸರ್ಚ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಸರಳವಾಗಿ ಅನುಸರಿಸಲು ಸಾಧ್ಯವಿಲ್ಲ ಏಕೆಂದರೆ ಇದು ತಿರುಗುವ ವಿಂಗಡಿಸಲಾದ ರಚನೆಯಾಗಿದೆ. ಆದ್ದರಿಂದ, ಸಾಮಾನ್ಯ ಬೈನರಿ ಹುಡುಕಾಟಕ್ಕಿಂತ ಸ್ವಲ್ಪ ಮಾರ್ಪಾಡು ಇದೆ.

ಆದ್ದರಿಂದ, ಸಾಮಾನ್ಯವಾಗಿ ಬೈನರಿ ಹುಡುಕಾಟದಲ್ಲಿ, ಪ್ರಸ್ತುತ ಅಂಶ (ಮಧ್ಯ ಸೂಚ್ಯಂಕದಲ್ಲಿರುವ ಅಂಶ) ಗುರಿಯಂತೆಯೇ ಇದೆಯೇ ಎಂದು ನಾವು ಪರಿಶೀಲಿಸುತ್ತೇವೆ, ನಂತರ ನಾವು ಅದರ ಸೂಚಿಯನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತೇವೆ. ಈ ಹಂತವು ಇಲ್ಲಿ ಒಂದೇ ಆಗಿರುತ್ತದೆ. ಅದನ್ನು ಹೊರತುಪಡಿಸಿ, ಅವು ಒಂದೇ ಆಗಿಲ್ಲದಿದ್ದರೆ, ಪಿವೋಟ್ [ಪ್ರಸ್ತುತ ಅಂಶದ ಅಥವಾ ಎಡಕ್ಕೆ ಬಲಕ್ಕೆ ಇದೆಯೇ ಎಂದು ನಾವು ಪರಿಶೀಲಿಸುತ್ತೇವೆ. ಅದು ಬಲಭಾಗದಲ್ಲಿದ್ದರೆ, ಗುರಿಯು ತಿರುಗಿಸದ ಸಬ್‌ರೇರ್‌ನಲ್ಲಿದೆ ಎಂದು ನಾವು ಪರಿಶೀಲಿಸುತ್ತೇವೆ, ಅದು ಹೆಚ್ಚಿನದನ್ನು ನಾವು ನವೀಕರಿಸಿದರೆ ನಾವು ಕಡಿಮೆ ನವೀಕರಿಸುತ್ತೇವೆ. ಅಂತೆಯೇ, ಪಿವೋಟ್ ಎಡಭಾಗದಲ್ಲಿದ್ದರೆ, ಗುರಿ ತಿರುಗಿಸದ ಸಬ್‌ರೇರ್‌ನಲ್ಲಿದೆ ಎಂದು ನಾವು ಮತ್ತೆ ಪರಿಶೀಲಿಸುತ್ತೇವೆ, ನಾವು ಕಡಿಮೆ ನವೀಕರಿಸುತ್ತೇವೆ, ಇಲ್ಲದಿದ್ದರೆ ನಾವು ಹೆಚ್ಚಿನದನ್ನು ನವೀಕರಿಸುತ್ತೇವೆ. ಮತ್ತು ಕೊನೆಯಲ್ಲಿ, ನಾವು ಲೂಪ್ನಿಂದ ಹೊರಬಂದರೆ, ನಿರ್ದಿಷ್ಟ ಶ್ರೇಣಿಯಲ್ಲಿ ಗುರಿ ಇರುವುದಿಲ್ಲ ಎಂದು ನಮಗೆ ಖಚಿತವಾಗಿದೆ.

ಸಹ ನೋಡಿ
Sqrt (x) ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ

ತಿರುಗಿದ ವಿಂಗಡಿಸಲಾದ ಅರೇ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ಹುಡುಕಾಟಕ್ಕಾಗಿ ಆಪ್ಟಿಮೈಸ್ಡ್ ಕೋಡ್

ಸಿ ++ ಕೋಡ್

#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);
}

ಜಾವಾ ಕೋಡ್

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));
    }
}

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಲಾಗ್ ಎನ್), ಗುರಿ ಅಂಶವನ್ನು ಕಂಡುಹಿಡಿಯಲು ನಾವು ಬೈನರಿ ಹುಡುಕಾಟವನ್ನು ಬಳಸಿದ್ದೇವೆ. ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ಲಾಗರಿಥಮಿಕ್ ಆಗಿದೆ.

ಸಹ ನೋಡಿ
ಯಾವುದೇ ಎರಡು ಅಂಶಗಳ ನಡುವೆ ಕನಿಷ್ಠ ವ್ಯತ್ಯಾಸವನ್ನು ಹುಡುಕಿ

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (1), ನಾವು ಕೆಲವು ಸ್ಥಿರ ಸಂಖ್ಯೆಯ ಅಂಶಗಳನ್ನು ಮಾತ್ರ ಸಂಗ್ರಹಿಸಿರುವುದರಿಂದ, ಸ್ಥಳದ ಸಂಕೀರ್ಣತೆಯು ಸ್ಥಿರವಾಗಿರುತ್ತದೆ.