二进制搜索1/4修改

-1

我的任务是编写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策略来做到这一点？最难的部分是让它记住它已经分裂了一半：/

来源

2014-09-21 Ophelia

'它不工作'为什么？编译错误？运行时错误？错误的输出？如果它给出了错误的答案 - 请提供一个测试案例+预期的和实际的结果来证明问题。你也应该使用一个调试器（或者更好，将代码拆分成更小的方法并编写单元测试，现在bu调试器会很好）。 – amit 2014-09-21 06:42:02

你的公式确定的主要是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这样的非法索引以指示该项目未找到。

来源

2014-09-21 09:36:04

二进制搜索1/4修改

回答

相关问题