欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

使用递归实现二分查找算法(查找一个值的索引)

程序员文章站 2022-07-12 09:35:18
...

1.前提

	查找的序列必须是有序的

代码实现

package binarySearch;

import java.util.Scanner;

/**
 * @program: 7.查找的相关操作
 * @description: 主方法
 * @author: Zhou Jian
 * @create: 2020-07-16 16:37
 */
public class main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int[] Array = {3, 4, 5, 6, 7, 8, 9};
        System.out.println("请输入你要查询的数:");
        int num = s.nextInt();
        int index = binarySearch(Array, 0, Array.length - 1, num);
        System.out.printf("%d的下标是:%d", num ,index);
    }
    /**
     * 二分查找算法
     *
     * @param array 数组
     * @param left  左指针
     * @param right 右指针
     * @param key   要查找的值
     * @return 如果找到,则返回其下标,否则返回-1
     */
    public static int binarySearch(int[] array, int left, int right, int key) {
        // 查找失败
        if (left > right) {
            return -1;
        }
        int mid = (left + right) / 2; // 中间值的下标
        int midKey = array[mid]; // 中间值
        // 如果大于中间值,则向右递归
        if (key > midKey) {
            return binarySearch(array, mid + 1, right, key);
        } else if (key < midKey) { // 否则,向左递归
            return binarySearch(array, left, mid - 1, key);
        } else{ // 成功找到
            return mid;
        }
    }
}