-
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathTernary-search.cpp
80 lines (74 loc) · 2.05 KB
/
Ternary-search.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/* Program to search data in given array using ternary search */
#include <iostream>
using namespace std;
// Function to search data in a given array
int Ternary_search(int *arr,int l,int r,int to_search)
{
//split current array into 3 part
int Mid1=l+(r-l)/3,Mid2=r-(r-l)/3;
// data not found condition
if(l>r)
return -1;
// if data found in Mid1 index then return index number
else if(arr[Mid1]==to_search)
return Mid1;
// if data found in Mid2 index then return the index number
else if(arr[Mid2]==to_search)
return Mid2;
//else if data not found at index Mid1 and Mid2 then search in middle part of array
else if(arr[Mid1]<to_search&&arr[Mid2]>to_search)
{
Mid1=Mid1+1;
Mid2=Mid2-1;
}
// if data is less than Mid index data then search in before index number of current
else if(arr[Mid1]>to_search)
{
Mid2=Mid1-1;
Mid1=l;
}
// if data is less than Mid index data then search in after index number of current
else if(arr[Mid2]<to_search)
{
Mid1=Mid2+1;
Mid2=r;
}
// recursive calling the function
return Ternary_search(arr,Mid1,Mid2,to_search);
}
// driver code
int main()
{
int n,*arr,i,to_search,res;
cout<<"Enter size: ";
// taking input
cin>>n;
// if size is negative then make it positive one
if(n<0)
n=n*-1;
// dynamically allocating array
arr=(int*)malloc(sizeof(int)*n);
for(i=0;i<n;i++)
{
cin>>arr[i];
}
cout<<"Enter the number to search: ";
// taking data to search
cin>>to_search;
// calling function to search index of given number and assign it in res
res=Ternary_search(arr,0,n,to_search);
// if res contain -1 that means data not found
if(res==-1)
cout<<"Data Not Found";
else
cout<<"Data found at index no: "<<res;
return 0;
}
/*
Input: Enter size: 5
1,2,3,4,5
Enter the number to search: 2
Output: Data found at index no: 1
Time complexity: O(log3 n)
Space complexity: O(1)
*/