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

Java实现二分查找(递归和非递归)

程序员文章站 2022-03-14 20:42:09
...

 

二分查找递归实现

package com.utunan;

public class Search {


    /**
     * 二分查找
     *
     * @param nums   : 待查数组
     * @param target : 需要查询的数字
     * @return :返回查询数字在数组中的下标,-1表示不存在该数字
     * @description: 递归实现
     */
    public static int binarySearch(int[] nums, int start, int end, int target) {

        if (nums == null || nums.length == 0) {
            return -1;
        }

        int middle = (start + end) / 2;

        if (start >= end) {
            return -1;
        }

        if (nums[middle] == target) {
            return middle;
        } else if (nums[middle] > target) {
            return binarySearch(nums, start, middle - 1, target);
        } else {
            return binarySearch(nums, middle + 1, end, target);
        }

    }
    
}

 

二分查找非递归实现

/**
     * 二分查找
     *
     * @param nums   : 待查数组
     * @param target : 需要查询的数字
     * @return :返回查询数字在数组中的下标,-1表示不存在该数字
     * @description: 非递归实现
     */
    public static int binarySearch(int[] nums, int target) {

        if(nums == null || nums.length == 0) {
            return -1;
        }

        int low = 0;
        int high = nums.length;

        while (low <= high) {

            int middle = (high + low) / 2;

            if (nums[middle] == target) {
                return middle;
            } else if (nums[middle] > target) {
                low = middle + 1;
            } else {
                high = middle - 1;
            }

        }
        return -1;
    }