Document

Ternary Search

Ternary search is a search algorithm that is used to find the position of a target value within a sorted array. It operates on the principle of dividing the array into three parts instead of two, as in binary search. The basic idea is to narrow down the search space by comparing the target value with elements at two points that divide the array into three equal parts.






Algorithm Visualization
-84 -51 -12 0 5 14 19 27 59 45 48 71 100 124 190 227 280 299 550








Complexity

Worst Case O( log3 N )
Average Case O( log3 N )
Best Case O( 1 ) 
int ternarySearch(int l, int r, int key, int ar[]) {
    if (r >= l) {
        int mid1 = l + (r - l) / 3;
        int mid2 = r - (r - l) / 3;

        if (ar[mid1] == key) {
            return mid1;
        }
        if (ar[mid2] == key) {
            return mid2;
        }

        if (key < ar[mid1]) {
            return ternarySearch(l, mid1 - 1, key, ar);
        } else if (key > ar[mid2]) {
            return ternarySearch(mid2 + 1, r, key, ar);
        } else {
            return ternarySearch(mid1 + 1, mid2 - 1, key, ar);
        }
    }
    return -1;
}

int main() {
    int l, r, p, key;
    int ar[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    l = 0;
    r = 9;

    printf("Enter the key to search: ");
    scanf("%d", &key);

    p = ternarySearch(l, r, key, ar);

    if (p != -1) {
        printf("Index of %d is %d\n", key, p);
    } else {
        printf("Index of %d not found\n", key);
    }

    return 0;
}
            
    
class TernarySearch {
    
    static int ternarySearch(int l, int r, int key, int ar[]) {
        if (r >= l) {
            int mid1 = l + (r - l) / 3;
            int mid2 = r - (r - l) / 3;
    
            if (ar[mid1] == key) {
                return mid1;
            }
            if (ar[mid2] == key) {
                return mid2;
            }
    
            if (key < ar[mid1]) {
                return ternarySearch(l, mid1 - 1, key, ar);
            } else if (key > ar[mid2]) {
                return ternarySearch(mid2 + 1, r, key, ar);
            } else {
                return ternarySearch(mid1 + 1, mid2 - 1, key, ar);
            }
        }
        return -1;
    }
    
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int l, r, p, key;
        int ar[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        l = 0;
        r = ar.length - 1;
    
        System.out.print("Enter the key to search: ");
        key = sc.nextInt();
    
        p = ternarySearch(l, r, key, ar);
    
        if (p != -1) {
            System.out.println("Index of " + key + " is " + p);
        } else {
            System.out.println("Index of " + key + " not found");
        }
    }
}

    
def ternarySearch(l, r, key, ar):
    if r >= l:
        mid1 = l + (r - l) // 3
        mid2 = r - (r - l) // 3

        if ar[mid1] == key:
            return mid1
        if ar[mid2] == key:
            return mid2

        if key < ar[mid1]:
            return ternarySearch(l, mid1 - 1, key, ar)
        elif key > ar[mid2]:
            return ternarySearch(mid2 + 1, r, key, ar)
        else:
            return ternarySearch(mid1 + 1, mid2 - 1, key, ar)

    return -1

if __name__ == "__main__":
    ar = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    l = 0
    r = len(ar) - 1

    key = int(input("Enter the key to search: "))

    p = ternarySearch(l, r, key, ar)

    if p != -1:
        print(f"Index of {key} is {p}")
    else:
        print(f"Index of {key} not found")