首页 > 代码库 > 二分查找的循环实现和递归实现

二分查找的循环实现和递归实现

2024-07-17 14:18:20   226人阅读

自己实现了二分查找的循环实现和递归实现

说明：二分查找适用于顺序存储结构，不适于链式存储结构，是一个高效的查找方法。虽然折半查找效率高，但是要排序，排序本身是一种很费时的运算。
    要求传入的表是有序的。
    二分查找的过程可用二叉树描述，把当前区间的中点位置上的元素作为根，左子表和右子表中的元素分别作为根的左子树和右子树，由此得到二叉树。
    此树称为描述折半查找的判定树或比较树。

package lirui.find;

/**
 * Created by lirui on 14-8-14.
 */
public class BinarySearch {

    /**
     * 二分查找法要求传入的参数是有序的，且从小到大递增。
     * 循环的方式实现。
     *
     * @param list
     * @param key
     * @return
     */
    public static int mybinarySearch(int[] list, int key) {
        int low = 0, high = list.length, mid;
        int n = list.length;
        while (low <= high) {
            mid = (low + high) / 2;
            if (key == list[mid]) {
                return mid;
            }
            if (key < list[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }

    // 用递归算法实现二分查找
    public static int mybinarySearchRec(int[] list, int key, int low, int high) {
        int mid;
        if (low <= high) {
            mid = (low + high) / 2;
            if (key == list[mid]) {
                return mid;
            }
            if (key < list[mid]) {
                return mybinarySearchRec(list, key, low, mid - 1);
            } else {
                return mybinarySearchRec(list, key, mid + 1, high);
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] list = {2, 4, 6, 7, 9, 10, 33, 500};
        int result = mybinarySearch(list, 5);
        System.out.println(result);
        int result2 = mybinarySearchRec(list,5,0,7);
        System.out.println(result2);
    }
}



联系
我们