二分查找法实现及时间复杂度推演

文章目录

• 一、二分法简介

• 二、查找过程
  

• 三、算法要求

• 四、二分查找实现
  

• 五、时间复杂度
  

• 
  

一、二分法简介

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

二、查找过程

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

三、算法要求

1. 必须采用顺序存储结构。

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

   
   

四、二分查找实现

public static void main(String[] args) {
    int array[] = {3,5,11,17,21,23,28,30,32,50,64,78,81,95,101};
    System.out.println(binSerch(array,5,array.length-1,81));
}

/**
 *  递归实现
 * @param art 数组
 * @param start 开始下标
 * @param end   结束下标
 * @param key 需要查找的数值
 * @return
 */
public static int binSerch(int art[],int start,int end ,int key){
    int mid = (end + start)/2;
    if (art[mid] == key){
        return mid;
    }
    if (start >= end){
        return -1;
    }else if(key > art[mid]){
        return binSerch(art,mid+1,end,key);
    }else if(key < art[mid]){
        return binSerch(art,start,mid-1,key);
    }
    return -1;
}

五、时间复杂度

小编创建了一个关于Java学习讨论的微信群！想进去的可以联系小编！同时也欢迎大家点赞与转发！

小编微信：372787553

备注为进群，通过后小编会邀请您进群！