使用递归实现二分查找算法(查找一个值的索引)
程序员文章站
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;
}
}
}
下一篇: 写一个二分查找