介绍

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

要求

1、必须采用顺序存储结构

2、必须按关键字大小有序排列

基本思想

二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.util.Arrays;
import java.util.Scanner;

/**
 * @author LeDao
 * @company
 * @create 2021-06-21 12:38
 */
public class Test {

    public static void main(String[] args) {
        int[] arr = new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
        int index = 0;
        int result = -1;
        System.out.println("输入你要查找的数：");
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int start = 0, end = arr.length - 1;
        while (start <= end) {
            index++;
            int mid = start + (end - start) / 2;
            System.out.println("第" + index + "次: start=" + start + ",end=" + end + ",mid=" + mid);
            if (num < arr[mid]) {
                end = mid - 1;
            } else if (arr[mid] < num) {
                start = mid + 1;
            } else {
                result = mid;
                break;
            }
        }
        if (result == -1) {
            System.out.println("你要查找的数不存在！！");
            System.out.println("循环执行了" + index + "次");
        } else {
            System.out.println("你要查找的数的数组下标为：" + result);
            System.out.println("循环执行了" + index + "次");
        }
    }
}

结果

img img