二进制搜索1/4修改
问题描述:
我的任务是编写1/4 - 3/4二分查找算法修改,其中第一个元素比较,当在列表中搜索一个项目时,是'pivot'元素,它位于距离为 的1/4的距离(假设所选择的结束是'剩余' 列表的开始)。如果没有匹配('pivot'元素不等于搜索关键字),并且如果列表中应进一步检查以进行搜索的部分是列表的1/4th 部分,则继续使用相同的策略。每当 列表中应进一步检查的部分大小为3/4时,切换到 二进制搜索一次并返回到第1 /第4-3/4策略。 我的代码是在这里,但它不工作,我不知道,即使我在做正确的事:二进制搜索1/4修改
public static int ThreeFour(int[] Array,int item)
{
int counter =0;
int high=Array.length-1;
int low=0;
int pivot = 0;
boolean split = true;
boolean last =true;
while(high >= low) {
if(split){
pivot = (high+low)/4;
last=true;}
else
{ pivot = (high+low)/2;
split=true;
last=false;
}
if(Array[pivot] == item)
{ counter++;
System.out.println("Pivot"+pivot);
return counter;
}
if(Array[pivot] < item) {
low = pivot + 1;
counter++;
}
if(Array[pivot] > item) {
high = pivot - 1;
counter++;
if (last)
split=false;
}
}
return 0;
}
它不工作,也许有一个simplier策略来做到这一点?最难的部分是让它记住它已经分裂了一半:/
答
你的公式确定的主要是3/4分裂的错误。如果你想在某个时候c
与0 <= c <=1
分裂low
和high
之间的间隔,您可以:
pivot = low + c * (high - low)
= (1 - c) * low + c * high
此西港岛线给你low
为c == 0
,high
为c == 1
和为贵3/4拆分:
pivot = 0.75 * low + 0.25 * high
或与整数运算:
pivot = (3 * low + high)/4
特别是,low
和high
的因素要总结为1
我也认为你的函数有一个逻辑错误:您返回递归深度,这是没有意义的阵列。您应该返回数据透视表,即找到该项目的数组索引。这也意味着你失败时不能返回0,因为这是一个有效的数组索引。返回像-1这样的非法索引以指示该项目未找到。
'它不工作'为什么?编译错误?运行时错误?错误的输出?如果它给出了错误的答案 - 请提供一个测试案例+预期的和实际的结果来证明问题。你也应该使用一个调试器(或者更好,将代码拆分成更小的方法并编写单元测试,现在bu调试器会很好)。 – amit 2014-09-21 06:42:02