二分法查找递归方式

二分法,前提数据是有序的:

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);
        }

    }
}


打赏

未经允许请勿转载:老徐聊技术 » 二分法查找递归方式

分享到: +More

评论 沙了个发

换个身份

取消评论