🟡前言
21天挑战赛第二周,本文主要是讲述有关二分查找的知识
活动地址:CSDN21天学习挑战赛
🟡概述
二分查找适用于有序数组中
如下图所示,当我们要找到元素79时,先找数组的当中的元素81,由于79比81小,所以在左侧找(红框),重新定max和mid再寻找
🟡解题思路
- 先查找数组中最中间的元素(下标值向下取整)
- 如果要查找的元素值比中间的元素大,就将最大值改为中间值减一
max = mid - 1 - 如果要查找的元素值比中间的元素小,就将最小值改为中间值加一
min = mid + 1 - 重复上述步骤,直至找到所要查找的元素
🟡代码实现
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; } } } }
🟡结语
二分查找较简单,但是要注意数组一定要是有序的