二分法,前提数据是有序的:
package day04; public class test9 { public static void main(String[] args) { // 3.使用二分法查找有序数组中元素。找到返回索引,不存在输出-1。使用递归实现 int[] nums = { 1, 2, 3, 4, 5, 6, 7, 9,90 }; System.out.println(erfen(nums, 60, 0, nums.length-1)); } /** * 二分法查找(递归) * @param nums 要查找的数组 * @param m 要查找的值 * @param left 左边最小值 * @param right 右边最大值 * @return 返回值 成功返回索引,失败返回-1 */ public static int erfen(int[] nums, int m, int left, int right) { int midIndex = (left + right) / 2; //因为是二分法查找要求有序数组,所以超出数组边界的肯定都是查找不到的,左边小于右边也是不能查找的 if (m < nums[left] || m > nums[right] || nums[left] > nums[right]) { return -1; } //找中间值 int midValue = nums[midIndex]; if (midValue == m) { return midIndex; } else if (midValue > m) { //如果中间值大于要找的值则从左边一半继续递归 return erfen(nums, m, left, midIndex); } else { //如果中间值小于要找的值则从右边一半继续递归 return erfen(nums, m, midIndex, right); } } }