CrabSaberV is here
0%

二分查找

发表于 更新于 分类于

查找算法——二分查找

比较基础的查找算法，前提是在有序数据中查找。

思路

二分的思路还是比较简单的，也是分治思想。获取序列中间数与目标数进行比较，如果相等则找到，否则根据大于或小于划分前或右部分的序列继续进行同样操作。

一般情况有划分期间找到目标数，或者划分到不可划分的情况下找到或没找到。

步骤：

  1. 计算序列中间下标mid

  2. 将mid的值与target进行比较，如果相等则返回结果。

  3. 如果mid大于target,那么取mid之前的序列部分继续进行二分查找。

  4. 如果mid小于target,那么取mid之后的序列继续进行二分查找。

  5. 如果中间找到target则返回下标，没有找的则可以返回-1作为数据没有找到标志。

    代码

    前提是数组不为空，数组升序排列，如果数据不在数组中返回-1。

    递归方案

    递归还是比较简单易懂的。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public int BinSearch(int[] nums,int start,int end,int target){
        if(start > end){
            return -1;
        }
        int mid = start + (end - start)/2;
        if(nums[mid] > target){
            return BinSearch(nums,start,mid-1,target);
        }else if(nums[mid] < target){
            return BinSearch(nums,mid+1,end,target);
        }

        return mid;
            
    }

迭代方案

一般情况迭代方法都是比较推荐的，毕竟可以无视深度，递归会因为深度增加而导致内存栈溢出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int BinSearch(int[] nums,int target){
        // 迭代不一定必须用stack来处理，需要看情况。

        int l = 0;
        int r = nums.Length-1;

        int result = -1;
        while(l <= r){
            int mid = l + (r-l)/2;
            if(nums[mid] == target){
                result = mid;
                break;
            }else if(nums[mid] > target){
                // 往前找
                r = mid - 1;
            }else{
                // 往后找
                l = mid + 1;
            }
        }

        return result;
        
    }

复杂度

平均为O(logn)。

最好就是O(1)。