Java算法笔记_026:折半摸索(Java)

目录

1 style=”font-family: 行草;”>问题讲述

2 style=”font-family: 金鼎文;”>解决方案

2.1 style=”font-family: 宋体;”>递归法

2.2 style=”font-family: 宋体;”>迭代法

 

 


1 问题讲述

首先,领会一下哪儿为折半招来?此处,借用《算法设计及分析基础》第三版及一样段子文字介绍:

 Java 1

 

 

 


2 解决方案

2.1 递归法

 具体代码如下:

package com.liuzhen.chapter4;

public class BinarySearch {
    //方法1:递归求解
    public void recursionSearch(int[] A,int start,int end,int number){
        int mid = (start + end)/2;
        if(A[mid] == number)
            System.out.println("使用递归法求取number = "+number+"的数组下标结果:"+mid);
        if(A[mid] > number)
            recursionSearch(A,start,mid-1,number);   //递归调用
        if(A[mid] < number)
            recursionSearch(A,mid+1,end,number);     //递归调用
    }


    public static void main(String[] args){
        BinarySearch test = new BinarySearch();
        int[] A = {3,14,27,31,39,42,55,70,74,81,85,93,98};
        test.recursionSearch(A, 0, A.length-1, 70);
    }
}

运行结果:

使用递归法求取number = 70的数组下标结果:7

 

2.2 迭代法

 具体代码如下:

package com.liuzhen.chapter4;

public class BinarySearch {

    //方法2:迭代求解
    public int iterationSearch(int[] A,int number){
        int start = 0;
        int end = A.length-1;
        while(start <= end){
            int mid = (start + end)/2;
            if(A[mid] == number)
                return mid;
            if(A[mid] > number)
                end = mid-1;
            if(A[mid] < number)
                start = mid+1;
        }
        return -1;
    }

    public static void main(String[] args){
        BinarySearch test = new BinarySearch();
        int[] A = {3,14,27,31,39,42,55,70,74,81,85,93,98};
        System.out.println("使用迭代法求解number = 70的数组下标结果:"+test.iterationSearch(A, 70));
    }
}

运转结果:

使用迭代法求解number = 70的数组下标结果:7

 

相关文章