（Java）类似于Binary的搜索，但是使用/ 3而不是/ 2 [英] (Java) A search similar to Binary but using /3 instead of /2
问题描述
我创建了一个程序，该程序比较不同的搜索方法，这些方法从0-999的排序数组中搜索随机int值0-999。我已经创建了一个二进制搜索，该搜索可以完美地工作，然后，我决定尝试创建一个搜索，而不是将值分成两半，而是将它们分为1/3和2/3。
所以基本上如果我有
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}
和我正在寻找10，我将从上方转到
{6,7,8,9,10,11,12,13,14,15}
到
{10,11,12 ，13,14,15}
到
{10,11}
然后是
简单{10}，并返回该值的索引。
我目前有：
int loopTotal3 = 0;
for（int y = 0; y< 1000; y ++）{
System.out.println（ Reference1）;
int first = 0;
int last = array0Through999.length-1;
int third =（array0Through999 [0] + array0Through999 [999]）/ 3;
int findThis3 = rand.nextInt（1000）;
int loop3 = 0;
while（first< = last）{
System.out.println（ Reference2）;
loop3 ++;
if（array0Through999 [third]< findThis3）{
System.out.println（ Reference3）;
first =第三+ 1；
}
else if（array0Through999 [third] == findThis3）{
System.out.println（ Reference4）;
休息时间；
}
else {
System.out.println（ Reference5）;
last = third-1；
}
第三=（第一个+最后一个）/ 3;
}
loopTotal3 = loopTotal3 + loop3;
}
int loopAverage3 = loopTotal3 / 1000;
System.out.println（二进制搜索的平均次数为： + loopAverage3 + \n）；
当前代码在执行第一个if语句时一直卡住，我对此并不满意。 / p>
关于我的问题的任何想法，或者这种逻辑是否正确？
导入java.util.Random;
公共类weqfgtqertg {
public static void main（String args []）{
int array0Through999 [] = {0,1，...，999};
int loopTotal3 = 0;
Random rand = new Random（）;
for（int y = 0; y< 1000; y ++）{
//System.out.println(\"Reference1）;
System.out.println（y）;
int first = 0;
int last = array0Through999.length-1;
int第三=（第一个+最后一个）/ 3;
int findThis3 = rand.nextInt（1000）;
int loop3 = 0;
while（first< = last）{
//System.out.println(\"Reference1）;
loop3 ++;
if（array0Through999 [third]< findThis3）{
//System.out.println(\"Reference3）;
first = Third + 1;
}
else if（array0Through999 [third] == findThis3）{
//System.out.println(\"Reference4）;
休息时间；
}
else {
//System.out.println(\"Reference5）;
last = third-1；
}
int calc = last-first;
第三=首+（calc / 3）;
} //结束，而
loopTotal3 = loopTotal3 + loop3;
} //结束
int loopAverage3 = loopTotal3 / 1000;
System.out.println（第三次搜索的平均次数为： + loopAverage3）;
}
}
自从我发布这个问题以来已经有一段时间了，但是我终于解决了我的问题。对于可能偶然发现此错误的人，这是正确的代码。
编辑：数组中包含 ...，以使其不会令人讨厌地阅读或投入使用屏幕。我将数组中的所有0-999都进行了硬编码。
I have created a program which compares different search methods which search for a random int value 0-999 from a sorted array which is 0-999. I have created a binary search which works perfectly and after doing this I decided to try to create a search which, instead of splitting the values into half, splits them into 1/3 and 2/3 depending. So basically if I have {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15} and I was looking for 10 I would go from above to {6,7,8,9,10,11,12,13,14,15} to {10,11,12,13,14,15} to {10,11} then simple {10} and return the index of this value.
I currently have:
int loopTotal3 = 0;
for(int y = 0; y < 1000; y++){
System.out.println("Reference1");
int first = 0;
int last = array0Through999.length - 1;
int third = (array0Through999[0] + array0Through999[999]) / 3;
int findThis3 = rand.nextInt(1000);
int loop3 = 0;
while(first <= last){
System.out.println("Reference2");
loop3++;
if (array0Through999[third] < findThis3){
System.out.println("Reference3");
first = third + 1;
}
else if(array0Through999[third] == findThis3){
System.out.println("Reference4");
break;
}
else{
System.out.println("Reference5");
last = third-1;
}
third = (first + last) / 3;
}
loopTotal3 = loopTotal3 + loop3;
}
int loopAverage3 = loopTotal3 / 1000;
System.out.println("The average number of times for a Binary Search is: " + loopAverage3 + "\n");
The code is currently getting stuck running through the first if statement and I am not positive of why.
Any ideas about my issue or if this logic is close to correct?
import java.util.Random;
public class weqfgtqertg {
public static void main(String args[]) {
int array0Through999[] = {0,1,...,999};
int loopTotal3 = 0;
Random rand = new Random();
for(int y = 0; y < 1000; y++){
//System.out.println("Reference1");
System.out.println(y);
int first = 0;
int last = array0Through999.length - 1;
int third = (first + last) / 3;
int findThis3 = rand.nextInt(1000);
int loop3 = 0;
while(first <= last) {
//System.out.println("Reference1");
loop3++;
if (array0Through999[third] < findThis3){
//System.out.println("Reference3");
first = third+1;
}
else if(array0Through999[third] == findThis3){
//System.out.println("Reference4");
break;
}
else{
//System.out.println("Reference5");
last = third-1;
}
int calc = last - first;
third = first + (calc/3);
}//end while
loopTotal3 = loopTotal3 + loop3;
}//end for
int loopAverage3 = loopTotal3 / 1000;
System.out.println("The average number of times for a Tertiary Search is: " + loopAverage3);
}
}
It has been a while since I posted this question but I finally got around to solving my issue. Here is the correct code for anyone who may stumble upon this.
edit: The array includes the "..." to make this not obnoxious to read or put out onto the screen. I had all 0-999 within my array hard coded.
这篇关于（Java）类似于Binary的搜索，但是使用/ 3而不是/ 2的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
