🟡前言

21天挑战赛第二周，本文主要是讲述有关二分查找的知识

活动地址：CSDN21天学习挑战赛

🟡概述

二分查找适用于有序数组中

如下图所示，当我们要找到元素79时，先找数组的当中的元素81，由于79比81小，所以在左侧找（红框），重新定max和mid再寻找

🟡解题思路

1. 先查找数组中最中间的元素（下标值向下取整）
2. 如果要查找的元素值比中间的元素大，就将最大值改为中间值减一
   max = mid - 1
3. 如果要查找的元素值比中间的元素小，就将最小值改为中间值加一
   min = mid + 1
4. 重复上述步骤，直至找到所要查找的元素

🟡代码实现

public class BinarySearch {

    public static void main(String[] args) {
        // input data
        int[] a = {7,23,79,81,103,127,131,147};
        int key = 11;
        // 调用算法，并输出结果
        int result = search(a, key);
        System.out.println(result);
    }

    private static int search(int[] a,int key){
        // 初始化变量
        int min = 0;
        int max = a.length - 1;
        //通过循环找到要查找的元素
        while (true){
        	int mid = (max + min) / 2 ;
        	
        	if(min > max){
				return -1;
			}
			
            // 情况1：比key大
            }else if(a[mid] > key){
                max = mid - 1;
                
            // 情况2：比key小     
            }else if(a[mid] < key){
                min = mid + 1;
            }
            
            //情况3：找到了
			else{
				return mid;
			}
        } 
    }
}

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

🟡结语

二分查找较简单，但是要注意数组一定要是有序的