This page looks best with JavaScript enabled

二分查找

 ·  ☕ 2 min read

二分查找算法是一种在有序数组中查找某一特定元素的搜索算法,时间复杂度是 O(logn) 。

这里用 Rust 实现一个简单的二分查找算法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
fn binary_search(arr: Vec<i32>, n: i32, hkey: i32) -> i32 {
    let mut low = 0;
    let mut high = n - 1;

    while low <= high {
        let mid = low + ((high - low) >> 1);
        if arr[mid as usize] == hkey {
            return mid;
        } else if arr[mid as usize] < hkey {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    -1
}

其中, low、high、mid 都是数组下标。low 和 high 表示当前查找的区间范围,mid 表示 [low, high] 的中间位置。
通过比较 arr[mid] 与 hkey 的大小,更新查找区间范围。直到找到或者区间缩小为0。

  1. 退出条件是:low<=high,而还是 low<high
  2. mid = low + ((high-low)>>1) 考虑 mid=(low+high)/2 当 low 和 high 比较大时,二者之和有可能会溢出。

下面看几个来自《数据结构与算法之美》中的几个变种问题。

查找第一个值等于给定值的元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
fn binary_search(arr: Vec<i32>, n: i32, hkey: i32) -> i32 {
    let mut low = 0;
    let mut high = n - 1;

    while low <= high {
        let mid = low + ((high - low) >> 1);

        if arr[mid as usize] > hkey {
            high = mid - 1;
        } else if arr[mid as usize] < hkey {
            low = mid + 1;
        } else {
            if mid == 0 || arr[(mid-1) as usize] != hkey {
                return mid;
            }
            high = mid-1;
        }
    }
    -1
}

思路分析:arr[mid] 与 hkey 的比较有三种情况:大于,小于,等于。arr[mid]>hkey 时,需要更新 high=mid-1;arr[mid]<hkey 时,需要更新 low=mid+1;
而当 arr[mid]==hkey 时,则需要确定 arr[mid] 是不是第一个值等于给定值的元素。

如果 mid 等于 0 ,那么这个元素已经是数组的第一个元素,那么它肯定是我们要找的。如果 mid 前一个元素不等于 hkey,那么这个值也是我们要找的。
如果 arr[mid-1]==hkey 呢?说明 arr[mid] 不是第一个值等于给定值的元素,要找的值在 [low, mid-1] 范围中,
所以我们要更新 high=mid-1;

查找最后一个值等于给定值的元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
fn binary_search(arr: Vec<i32>, n: i32, hkey: i32) -> i32 {
    let mut low = 0;
    let mut high = n - 1;

    while low <= high {
        let mid = low + ((high - low) >> 1);

        if arr[mid as usize] > hkey {
            high = mid - 1;
        } else if arr[mid as usize] < hkey {
            low = mid + 1;
        } else {
            if mid == n-1 || arr[(mid+1) as usize] != hkey {
                return mid;
            }
            low = mid+1;
        }
    }
    -1
}

同问题一的解决思路相同,只是在确定目标值的时候,确定的条件变成了 mid==n-1 || arr[mid+1] != hkey

查找第一个大于等于给定值的元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
fn binary_search(arr: Vec<i32>, n: i32, hkey: i32) -> i32 {
    let mut low = 0;
    let mut high = n - 1;
    while low <= high {
        let mid = low + ((high - low) >> 1);
        if arr[mid as usize] >= hkey {
            if mid == 0 || arr[mid as usize - 1] < hkey {
                return mid;
            }
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    -1
}

也是相同的思路,在 arr[mid]>=hkey 时,检查 arr[mid-1] 是否小于 hkey。相应地缩小查找范围。

查找最后一个小于等于给定值的元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
fn binary_search(arr: Vec<i32>, n: i32, hkey: i32) -> i32 {
    let mut low = 0;
    let mut high = n - 1;
    while low <= high {
        let mid = low + ((high - low) >> 1);
        if arr[mid as usize] <= hkey {
            if mid == n - 1 || arr[mid as usize + 1] > hkey {
                return mid;
            }
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    -1
}
Share on

Serendipity
WRITTEN BY
Serendipity
iOS/Golang/Rust

What's on this Page