黑马程序员技术交流社区

标题: 使用递归完成阶乘和二分法查询 [打印本页]

---

作者: qbtx60266    时间: 2018-8-2 22:34
标题: 使用递归完成阶乘和二分法查询
public class Jiecheng {
    public static void main(String[] args) {
        System.out.println(jiecheng(5));
    }
    public static int jiecheng(int n){
        if(n == 1){
            return 1;
        }else{
            return n * jiecheng(n - 1);
        }
    }
}
可以利用方法返回调用方法本身解决一些难题
重点注意递归的结束条件即可

import java.util.Scanner;
import java.util.ArrayList;

public class BinarySearchPractice {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        Scanner sc = new Scanner(System.in);
        while (true) {
            System.out.println("你所想要添加的数字为(键入-1即停止)：");
            int num = sc.nextInt();
            if (num == -1) {
                break;
            }
            list.add(num);
        }
        int[] arr = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            arr = list.get(i);
        }
        System.out.println("请输入你想检索的数字：");
        int num1 = sc.nextInt();
        sort(arr);
        System.out.println("已将你所输入数字冒泡排序（升序），结果为：");
        printArray(arr);
        System.out.println("开始二分查询");
        System.out.print(binarySearch(arr, 0, arr.length - 1, num1) + 1);
        System.out.println("位为本数字位列数字位置");
        System.out.println("若结果为0则表明本数组内不含该数字");
    }

二分法只能查询升序数组元素，所以先对目标数组进行排序，可以利用冒泡排序法

    public static void sort(int data[]) {
        for (int i = 0; i < data.length - 1; i++) {
            for (int j = 0; j < data.length - 1 - i; j++) {
                if (data[j] > data[j + 1]) {
                    int temp = 0;
                    temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                }
            }
        }
    }

二分法具体步骤

    public static int binarySearch(int[] data, int from, int to, int key) {
        if (key > data[data.length - 1] || key < data[0]) {
            return -1;
        }
        if (key == data[data.length - 1]) {
            return data.length - 1;
        }
        if (key == data[0]) {
            return 0;
        }
        if (from + 1 == to && (data[from] != key && data[to] != key)){
            return -1;
        }
        int mid = (from + to ) / 2;
        if (from < to) {
            if (data[mid] == key) {
                int temp = 1;
                int mid1 = mid;
                while(data[mid + 1] == key){
                    mid ++;
                    temp ++;
                }
                while(data[mid - temp] == key){
                    temp ++;
                }
                System.out.println("该数组中与所检索数相同数目为" + temp + "个");
                return mid1;
            } else if (key > data[mid]) {
                return binarySearch(data, mid, to, key);
            } else {
                return binarySearch(data, from, mid, key);
            }
        }
        return -1;
    }


遍历打印输出方法


    public static void printArray(int[] data) {
        for (int i = 0; i < data.length; i++) {
            System.out.print(data +" ");
        }
    }
}

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2