本帖最后由 qq2403956244 于 2015-6-17 19:33 编辑
- /**
- 折半查找 --->英文单词:bisearch
- @author q...4
- */
- /*
- 1.需求:改进楼主代码
- 2.思路:发现,楼主代码中有如下问题
- a.while循环,每执行一次循环都要调用一次本身,假如数很多效率低。
- b.循环条件需稍作修改。
- c.当 num >20时,比如 num=23 ,这时就会报错ArrayIndexOutOfBoundsException。
- 3.步骤:a.用一个while循环就可以完成查找。
- b.循环条件只需 头角标(索引) <= 尾角标。
- c.尾角标 = 数组.长度 - 1。
- */
- public class Bisearch
- {
- /**
- * @param args
- */
- //主函数
- public static void main(String[] args)
- {
- // TODO 自动生成的方法存根
- int[] array = {1,3,5,7,9,11,14,15,16,17,20};
- // 0 1 2 3 4 5 6 7 8 9 10 角标
- System.out.println("Index="+bisearch(array,0,array.length-1,20));
- }
- //定义一个方法判断需要查找的元素是否在数组中,是->直接返回结果,不是->返回-1 。(角标没有负数)
- public static int bisearch(int array[],int fromIndex,int endIndex,int num)
- {
- while(fromIndex <= endIndex) //half!=fromIndex&&half!=endIndex
- {
- int half = (fromIndex + endIndex)/2; //中角标。5,8,9,10
- if(num<array[half]) //20<11,20<16,20<17,20<20
- {
- endIndex = half-1; //return bisearch(array, fromIndex, half, num);
- }
- else if(num>array[half]) { //20>11,20>16,20>17
- //return bisearch(array, half+1, endIndex, num);
- fromIndex = half+1; //6,9,10
- }
- else
- {
- return half; //10
- }
- }
- //if(num == array[half])
- // return half;
- return -1;
- }
- }
复制代码
|