欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

二分查找

程序员文章站 2024-01-24 13:27:34
数组元素的查找 1. 线性查找方式 假如我们要在一个数组中找一个关键字key,可能浮现在大家脑海中的第一个方法就是一个for()循环进行线性查找,但是这种查找方式在数组元素个数很大的时候会很低效。原因如下: 该方法的执行时间随着数组个数的增长而线性增长 时间复杂度为O(n) 2. 二分查找法 具体实 ......

数组元素的查找

1. 线性查找方式

假如我们要在一个数组中找一个关键字key,可能浮现在大家脑海中的第一个方法就是一个for()循环进行线性查找,但是这种查找方式在数组元素个数很大的时候会很低效。原因如下:

  • 该方法的执行时间随着数组个数的增长而线性增长
  • 时间复杂度为O(n)

2. 二分查找法

具体实现步骤

前提:
数组必须被提前排好序了

  • 若关键字小于中间元素则在前一半元素继续查找
  • 若关键字大于中间元素则在后一半元素继续查找
  • 若关键字等于中间元素,则匹配成功,查找结束

时间复杂度

假设有n个元素长度的数组,进行第一次比较后还需要比较n/2个元素;第二次比较后,还需要比较n/2/2个元素;经过第k次比较后,还需要比较n/2^k个元素。当k=log2n时,还需要比较一个元素。所以总共的比较次数最坏情况下是:log2n+1。故时间复杂度为O(log2n+1)。

3. 源码描述

public class BinarySearch{
    public static binarySearch(int[] a,int key){
        int low = 0;
        int high = a.length;
        
        while(low >= high){
            int mid = (low+high)/2;
            if(key > a[mid]){
                low = mid + 1;
            }
            else if(key == a[mid])
                return mid;
            else
                high = mid - 1;
        }
        return -low-1;  //返回该查找应该插入的下标位置
    }
}

补充:

选择排序:
每次把第i个元素,与后面length-i个元素进行比较,把最小的元素位置和i号元素位置进行对调。

public static void selectSort(int[] a){
            //将每个元素和后面的所有元素进行比较,最小的放在第一个 
            for(int i = 0;i < a.length-1;i++){
                int currentMin = a[i];
                int currentIndex = i;
                
                for(int j = i+1;j < a.length;j++){
                    if(currentMin > a[j]){
                        currentMin = a[j];
                        currentIndex = j;
                    }
                }
                //最小元素不是本身则对调
                if(j!=i){
                    a[j] = a[i];
                    a[i] = currentMin;
                }
            }
        }

当然java.util.Arrays类有binarySearch()函数也可以实现二分查找的功能,但是对于初学者而言,了解其思想还是十分有必要的。