java编程基础(五)二分法查找

2020-10-26   121 次阅读


二分法查找逻辑分析

二分法查找是在一组有序数据中寻找目标值,并获得目标值所在的下标位置

二分法查找也叫折半查找,基本逻辑是每次都向中间位置找,然后缩小一半范围再向中间位置找,请看下面的示例:

a

查找结束时,低位下标和高位下标可以重叠,请看下面的演示:
·a

如果低位下标和高位下标交叉,则说明查找的目标值不存在。最终 lo 下标值则是目标值应插入的位置:

a

代码

package demo1;

import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

public class BinarySearch {
    public static void main(String[] args) {
        int[] a = rnd();
        Arrays.sort(a);
        System.out.println(Arrays.toString(a));
        System.out.print("请输入查找的目标值:");
        int t = new Scanner(System.in).nextInt();

        int index = binarySearch(a, t);
        if (index < 0) {
            System.out.println("找不到目标值");
        } else {
            System.out.println(t+"所在的下标位置:"+index);
        }
    }

    private static int binarySearch(int[] a, int t) {
        int lo = 0;
        int hi = a.length-1;
        int mid;
        while (lo <= hi) {
            mid = (lo+hi) / 2;
            if (a[mid] < t) {
                lo = mid+1;
            } else if (a[mid] > t) {
                hi = mid-1;
            } else {
                return mid;
            }
        }

        return -(lo+1);
    }

    static int[] rnd() {
        int[] a = new int[5 + new Random().nextInt(6)];

        for (int i = 0; i < a.length; i++) {
            a[i] = new Random().nextInt(100);
        }

        return a;
    }
}

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

毕生所求无它,爱与自由而已