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

二分算法总结

程序员文章站 2022-05-22 15:38:56
...

二分查找

简介

二分查找是一种算法,其输入是一个有序的元素列表。

如果要 查找的元素包含在列表中,二分查找返回其位置;否则返回null

拓展: 酒桌上玩的游戏 猜数字,就是典型的二分法,100以内的 7步以内肯定能找出这个数字 对于包含n个元素的列表,用二分查找最多需要log2n步,而简单查找最多需要n步。 时间复杂度:O(log2n)

基本思想

  1. 当数据量很大适宜采用该方法。
  2. 采用二分法查找时,数据需是排好序的
  3. 假设数据是按升序排序的,对于给定值key,从序列的中间位置mid开始比较:
  • 如果当前位置arr[mid]值等于key,则查找成功;
  • 若key小于当前位置值arr[mid],则在数列的前半段中查找arr[low,mid-1];
  • 若key大于当前位置值arr[mid],则在数列的后半段中继续查找arr[mid+1,high],
  • 直到找到为止,时间复杂度:O(log(n))

注意 二分法特点:有序 , 有界

二分算法写法

1. 非递归二分法

int binary( int *a, int key, int n )
{
    int low = 0, 
    high = n - 1, 
    mid  = (high+low)/2;
    
    while(low < high && a[mid] != key)
    {
        if(a[mid] < key) {
            low  = mid + 1;
        } else if(a[mid] > key) {
            high = mid - 1;
        }
        mid = (low+high)/2;
    }
    if(a[mid] == key) {
        return mid;
    }
    return -1;
}
复制代码

2. 递归二分法

int recurbinary(int *a, int key, int low, int high)
{
    int mid;
    if(high >= low) {
        mid = (high+low)/2;
        if(a[mid] == key) {
            return mid;
        }else if(a[mid] > key) {
            return recurbinary(a,key,low,mid -1);
        }else {
            return recurbinary(a,key,mid + 1,high);
        }
    }else {
        return -1;
    }
}
复制代码

3. OC写法

- (void)binarySearchWithSearchArray:(NSArray *)array searchNum:(NSinteger)key {
    NSInteger min,max,mid;
    min = 0;
    max = arr.count - 1;
    mid = (min + max) / 2;

    for (int i = 0; i <= max; i++) {
        if (arr[mid] == key) {
          NSLog(@"查找次数为--->%d次",i);  
          NSLog(@"寻找值位置为--->%ld",mid);
          return;
        }else if (arr[mid] > key) {
            max = mid - 1;
            mid = (min + max) / 2;
        }else if (arr[mid] < key) {
            min = mid + 1;
            mid = (min + max) / 2;
        }
    }
}
复制代码

复杂度

二分法复杂度

  • 二分法因为整个运算过程没有空间的改变,所以空间复杂度为O(1)
  • 循环的基本次数是log2N,所以时间复杂度为O(log2N)

复杂度简介

算法复杂度分为时间复杂度和空间复杂度:

  • 时间复杂度是指执行这个算法所需要的计算工作量;
  • 空间复杂度是指执行这个算法所需要的内存空间。

时间和空间(即寄存器)都是计算机资源的重要体现,而算法的复杂性就是体现在运行该算法时的计算机所需的资源多少.

最坏情况下的时间复杂度称最坏时间复杂度。 一般不特别说明,讨论的时间复杂度均是最坏情况下的时间复杂度

这样做的原因是:最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界,这就保证了算法的运行时间不会比任何更长。