Ternary Search
I have a problem with wirting an algorith for ternary search.
This is what I came up with, but it doesn't work properly
int left = 0;
int right = a.legnth - 1;
while(left<=right){
//I am sure that folowing two lines of code are wrong, but I do not know how to change them...
int middle1 = (left + right) /3;
int middle2 = (left + right) /3 *2;
if(a[middle1] == searchValue)
return middle1;
elseif(a[middle2] == searchValue)
return middle2;
elseif(searchValue < a[middle1] )
right = middle1-1;
elseif(searchValue > a[middle1] && searchValue < a[middle2] )
right = middle2-1;
left = middle1;
elseif(searchValue > a[middle2])
left = middle2
}
return -1
}
your problem is that in integer arithmetic the expression
(left + right)/3
does not necessarily give you a value between left and right.
for example (2 + 3) / 3 is 1
similar problem with your other expression.
What to do? shove the value back inside the required range if it ever falls out of that range.
Also in your third else if you could move the left value one higher.
Lastly, there is no advantage to doing a ternary search. Binary search works faster, takes less code and conveninely in integer math the expression
(left + right) / 2
does fall in range so you can avoid doing a range check.
else if(searchValue > a[middle1] && searchValue < a[middle2] )right = middle2-1;left = middle1;you should put { } in this else if.the main problem is lef+right/3. if you are using int, it's not a very good idea to use this logic.
HI,I think that you need calculate like this.left + ((rigth - left ) / 3) Thanks
Uffff I finally figured it out. Here is complete code, this works!!! :)
public int ternarySearch(int[] a, int searchValue){
int left = 0;
int right = a.length -1;
while(left < right){
//middle1 and middle2 are indexes of variables that divide tha array into 3 pieces
int middle1 = (right + left) / 3;
int middle2 = (right + left) / 3 * 2;
while(middle2 > a.length - 1){
middle2--;
}
if(a[middle1] == searchValue){
//if value that we are looking for is at first midpoint program returns the index
return middle1;
}else if(a[middle2] == searchValue){
//if value that we are looking for is at second midpoint program returns the index
return middle2;
}else if (searchValue < a[middle1]){
//if value is in the first piece of the array, index of the first midpoint - 1 becomes the right border
right = middle1 - 1;
}else if (searchValue > a[middle1] && searchValue < a[middle2]){
//if value is in the second piece of the array,
//index of the first midpoint becomes the left border, and right border is second midpoint2 - 1
left = middle1;
right = middle2 - 1;
}else if (searchValue > a[middle2])
left = middle2;
//if value is in the third piece of the array, index of the second midpoint becomes our left border
}
return -1;
}
> Uffff I finally figured it out. Here is complete> code, this works!!! :)What is this doing?while(middle2 > a.length - 1)middle2 will never be bigger then a.length - 1
there should be == sign, but it works anyway.
> What is this doing?
> while(middle2 > a.length - 1)
> middle2 will never be bigger then a.length
> - 1
(3 + 3)/ 3 * 2 == 4 which is not between 3 and 3
(2+3)/3 == 1 which is not between 2 and 3
One assumes that he was trying to follow the advice to insure that the results of the integer arithmetic remains in bounds. He followed the advice for the upper bound. Ignored the advice for the lower bound. Fortunately the lower bound is not so important IF you always start with arrays indexed from 0 - you will occasionally be searching outside the bounds of the search that you started with, but at least it will still be in the array.
He also ignored the advice to move left up to middle1 + 1 once he knows that middle1 is too low.
And lastly ignored the advice that ternery search is more complicated and slower that binary search.
Ternary search, by working in thirds, makes a search look like N log base 3 (N) which on the surface looks better than N log base 2(N) which is the runtime of binary search. But log base 3 (N) is just a constant factor (namely log base 3 (2) = .63...) times log base 2 (N)
So don't you get a benefit from multiplying the speed by a factor less than one? Yes, you would except for the fact that you now much check against two bounds instead of 1, so you do about twice as much work on each pass of a ternary search in order to achieve a speed up of .63. You multiplied by a factor of 2 inorder to get a .63 speed up.
Final result, it runs about 25% slower than good old simpler binary search. And that is not counting the fact that the split by 3 in integer arithmetic can go out of bounds are requires extra code to shove it in bounds.
