Ternary Search क्या है

Ternary search दो markers से guess करने जैसा है जो range को तीन हिस्सों में बांटते हैं, उस हिस्से को फेंकते हुए जो answer नहीं रख सकता।

In this page:

What is Ternary Search
How It Works
Reduce Range
Complexity
Use Cases

Syntax

markup

low, high = 0, len(arr) - 1
while low <= high:
    mid1 = low + (high - low) // 3
    mid2 = high - (high - low) // 3
    if arr[mid1] == target:
        return mid1
    if arr[mid2] == target:
        return mid2
    if target < arr[mid1]:
        high = mid1 - 1
    elif target > arr[mid2]:
        low = mid2 + 1
    else:
        low, high = mid1 + 1, mid2 - 1

What is Ternary Search

Ternary search current search range को एक के बजाय दो midpoints उपयोग करके roughly तीन equal हिस्सों में बांटता है, फिर यह decide करने के लिए target को दोनों midpoints से compare करता है कि range का कौन सा तीसरा हिस्सा सुरक्षित रूप से discard किया जा सकता है।

उदाहरण: What is Ternary Search

#include <iostream>
using namespace std;
int main() {
    int arr[] = {1,3,5,7,9,11,13};
    int lo = 0, hi = 6;
    int mid1 = lo + (hi - lo) / 3;
    int mid2 = hi - (hi - lo) / 3;
    cout << "mid1=" << arr[mid1] << " mid2=" << arr[mid2] << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        int[] arr = {1,3,5,7,9,11,13};
        int lo = 0, hi = 6;
        int mid1 = lo + (hi - lo) / 3;
        int mid2 = hi - (hi - lo) / 3;
        System.out.println("mid1=" + arr[mid1] + " mid2=" + arr[mid2]);
    }
}

arr = [1, 3, 5, 7, 9, 11, 13]
lo, hi = 0, 6
mid1 = lo + (hi - lo) // 3
mid2 = hi - (hi - lo) // 3
print("mid1=", arr[mid1], "mid2=", arr[mid2])

#include <stdio.h>
int main() {
    int arr[] = {1,3,5,7,9,11,13};
    int lo = 0, hi = 6;
    int mid1 = lo + (hi - lo) / 3;
    int mid2 = hi - (hi - lo) / 3;
    printf("mid1=%d mid2=%d\n", arr[mid1], arr[mid2]);
    return 0;
}

How It Works

दो values, आमतौर पर mid1 और mid2 कहलाती हैं, range को तीन sections में बांटती हैं; target को दोनों से compare करना determine करता है कि तीन में से कौन सा एक या दो section target नहीं रख सकते और आगे search से खत्म किए जा सकते हैं।

उदाहरण: How It Works

#include <iostream>
using namespace std;
int main() {
    int arr[] = {1,3,5,7,9,11,13}, target = 9;
    int lo = 0, hi = 6;
    int mid1 = lo + (hi - lo) / 3, mid2 = hi - (hi - lo) / 3;
    if (arr[mid1] == target) cout << "Found at mid1";
    else if (arr[mid2] == target) cout << "Found at mid2";
    else cout << "Not at either midpoint yet";
    return 0;
}

public class Main {
    public static void main(String[] args) {
        int[] arr = {1,3,5,7,9,11,13};
        int target = 9;
        int lo = 0, hi = 6;
        int mid1 = lo + (hi - lo) / 3, mid2 = hi - (hi - lo) / 3;
        if (arr[mid1] == target) System.out.println("Found at mid1");
        else if (arr[mid2] == target) System.out.println("Found at mid2");
        else System.out.println("Not at either midpoint yet");
    }
}

arr = [1, 3, 5, 7, 9, 11, 13]
target = 9
lo, hi = 0, 6
mid1 = lo + (hi - lo) // 3
mid2 = hi - (hi - lo) // 3
if arr[mid1] == target:
    print("Found at mid1")
elif arr[mid2] == target:
    print("Found at mid2")
else:
    print("Not at either midpoint yet")

#include <stdio.h>
int main() {
    int arr[] = {1,3,5,7,9,11,13}, target = 9;
    int lo = 0, hi = 6;
    int mid1 = lo + (hi - lo) / 3, mid2 = hi - (hi - lo) / 3;
    if (arr[mid1] == target) printf("Found at mid1\n");
    else if (arr[mid2] == target) printf("Found at mid2\n");
    else printf("Not at either midpoint yet\n");
    return 0;
}

Reduce Range

Comparison results के आधार पर, या तो leftmost तीसरा, rightmost तीसरा, या leftmost और rightmost दोनों तीसरे discard किए जाते हैं, बीच वाले तीसरे (या कुछ cases में दो-तिहाई range) को ही search जारी रखने के लिए छोड़ते हुए।

उदाहरण: Reduce Range

#include <iostream>
using namespace std;
int main() {
    int arr[] = {1,3,5,7,9,11,13}, target = 11;
    int lo = 0, hi = 6;
    int mid1 = lo + (hi - lo) / 3, mid2 = hi - (hi - lo) / 3;
    if (target < arr[mid1]) hi = mid1 - 1;
    else if (target > arr[mid2]) lo = mid2 + 1;
    else { lo = mid1 + 1; hi = mid2 - 1; }
    cout << "New range: [" << lo << "," << hi << "]" << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        int[] arr = {1,3,5,7,9,11,13};
        int target = 11;
        int lo = 0, hi = 6;
        int mid1 = lo + (hi - lo) / 3, mid2 = hi - (hi - lo) / 3;
        if (target < arr[mid1]) hi = mid1 - 1;
        else if (target > arr[mid2]) lo = mid2 + 1;
        else { lo = mid1 + 1; hi = mid2 - 1; }
        System.out.println("New range: [" + lo + "," + hi + "]");
    }
}

arr = [1, 3, 5, 7, 9, 11, 13]
target = 11
lo, hi = 0, 6
mid1 = lo + (hi - lo) // 3
mid2 = hi - (hi - lo) // 3
if target < arr[mid1]:
    hi = mid1 - 1
elif target > arr[mid2]:
    lo = mid2 + 1
else:
    lo, hi = mid1 + 1, mid2 - 1
print("New range:", [lo, hi])

#include <stdio.h>
int main() {
    int arr[] = {1,3,5,7,9,11,13}, target = 11;
    int lo = 0, hi = 6;
    int mid1 = lo + (hi - lo) / 3, mid2 = hi - (hi - lo) / 3;
    if (target < arr[mid1]) hi = mid1 - 1;
    else if (target > arr[mid2]) lo = mid2 + 1;
    else { lo = mid1 + 1; hi = mid2 - 1; }
    printf("New range: [%d,%d]\n", lo, hi);
    return 0;
}

Complexity

चूंकि हर step range को एक आधे के बजाय roughly एक-तिहाई तक घटाता है, ternary search को binary search की तुलना में per elimination step लगभग 1.71 गुना ज़्यादा comparisons चाहिए — appealing three-way idea के बावजूद, यह simple value lookup के लिए असल में binary search से तेज़ नहीं है।

उदाहरण: Complexity

#include <iostream>
using namespace std;
int main() {
    int n = 1000000;
    double ternarySteps = log(n) / log(3) * 2;
    double binarySteps = log(n) / log(2);
    cout << "Ternary needs ~1.71x more comparisons per elimination than binary" << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        int n = 1000000;
        System.out.println("Ternary needs ~1.71x more comparisons per elimination than binary");
    }
}

n = 1_000_000
print("Ternary needs ~1.71x more comparisons per elimination than binary")

#include <stdio.h>
int main() {
    printf("Ternary needs ~1.71x more comparisons per elimination than binary\n");
    return 0;
}

Use Cases

Ternary search की असली value unimodal functions पर है — functions जो strictly increase फिर strictly decrease करते हैं (या इसका उल्टा) — जहां यह maximum या minimum point efficiently ढूंढ सकता है, जो specific stored value search करने से अलग तरह की problem है।

उदाहरण: Use Cases

#include <iostream>
using namespace std;
int f(int x) { return -(x-5)*(x-5) + 20; }
int main() {
    int lo = 0, hi = 10;
    while (hi - lo > 2) {
        int mid1 = lo + (hi - lo) / 3, mid2 = hi - (hi - lo) / 3;
        if (f(mid1) < f(mid2)) lo = mid1 + 1; else hi = mid2 - 1;
    }
    cout << "Peak near x=" << lo << endl;
    return 0;
}

public class Main {
    static int f(int x) { return -(x-5)*(x-5) + 20; }
    public static void main(String[] args) {
        int lo = 0, hi = 10;
        while (hi - lo > 2) {
            int mid1 = lo + (hi - lo) / 3, mid2 = hi - (hi - lo) / 3;
            if (f(mid1) < f(mid2)) lo = mid1 + 1; else hi = mid2 - 1;
        }
        System.out.println("Peak near x=" + lo);
    }
}

def f(x):
    return -(x - 5) ** 2 + 20

lo, hi = 0, 10
while hi - lo > 2:
    mid1 = lo + (hi - lo) // 3
    mid2 = hi - (hi - lo) // 3
    if f(mid1) < f(mid2):
        lo = mid1 + 1
    else:
        hi = mid2 - 1
print("Peak near x=", lo)

#include <stdio.h>
int f(int x) { return -(x-5)*(x-5) + 20; }
int main() {
    int lo = 0, hi = 10;
    while (hi - lo > 2) {
        int mid1 = lo + (hi - lo) / 3, mid2 = hi - (hi - lo) / 3;
        if (f(mid1) < f(mid2)) lo = mid1 + 1; else hi = mid2 - 1;
    }
    printf("Peak near x=%d\n", lo);
    return 0;
}

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Binary Search on Answer Next Lesson → Jump Search