二分算法总结

我不是女神ヾ 2022-04-27 21:40 140阅读 0赞

# 二分查找 #

## 简介 ##

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

如果要 查找的元素包含在列表中，二分查找返回其位置;否则返回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)

#### 复杂度简介 ####

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

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

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

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

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