实现二分查找的方法

概念

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

要求

1. 必须采用顺序存储结构
2. 必须按关键字大小有序排列

实现过程

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
int[] is = {5, 7, 19, 21, 21, 34, 42, 69, 85, 88}; int target = 7;

0	1	2	3	4	5	6	7	8	9
5	7	19	21	21	34	42	69	85	88
low				middle					high
low		middle	high
low/middle	high
	low/middle/high

代码

1. 循环方式

package leif;

public class BinarySearch {
    public static void main(String[] args) {
        int[] is = {5, 7, 19, 21, 21, 34, 42, 69, 85, 88};
        System.out.println(binarySearch(is, 7));
    }

    public static int binarySearch(int[] is, int target) {
        int left = 0;
        int right = is.length - 1;

        while (left <= right) {
            int middle = left + (right - left) / 2;

            if (target < is[middle]) {
                right = middle - 1;
            } else if (target > is[middle]) {
                left = middle + 1;
            } else {
                return middle;
            }
        }

        return -1;
    }
}

2. 递归方式

package leif;

public class BinarySearch {
    public static void main(String[] args) {
        int[] is = {5, 7, 19, 21, 21, 34, 42, 69, 85, 88};
        System.out.println(binarySearch(is, 7));
    }

    public static int binarySearch(int[] is, int target) {
        return binarySearch(is, target, 0, is.length - 1);
    }

    public static int binarySearch(int[] is, int target, int left, int right) {
        if (left > right) {
            return -1;
        }

        int middle = left + (right - left) / 2;

        if (target < is[middle]) {
            return binarySearch(is, target, left, middle - 1);
        } else if (target > is[middle]) {
            return binarySearch(is, target, middle + 1, right);
        } else {
            return middle;
        }
    }
}

转载于:https://www.jianshu.com/p/237974488ce7