二分查找法(Binary_Search)

二分查找法

一.介绍

二分查找法是一种在计算机中快速查找相应内容的算法,它基于有序数组将其查找,在计算机中广泛使用,已经成为计算机中必不可少的算法,二分查找: 又称为 折半查找,二分查找,适合对已经排序好的数据集合进行查找,时间复杂度O(log2n),效率高。

二.逻辑

假设有一升序的数据集合{0, 1, 2, 3, 4, 5, 6, 7, 8}先找出升序集合中最中间的元素mid = 4,将数据集合划分为两个子集,将最中间的元素mid = 4和关键字key进行比较,如果等于key则返回,如果大于关键字key,则在前一个数据集合中查找,否则在后一个子集中查找,直到找到为止,如果没找到则返回-1

例如:

{0, 1, 2, 3, 4, 5, 6, 7, 8},我们需要查找元素3,第一次会把该数组一分为二

找到最中间的数mid = 4;将mid和3比较,此时发现mid > 3;所以会进入数组{0, 1, 2, 3,}(一共4个元素,我们需要找到索引(r+l)/2 的元素1.5,我们将其设置为整型所以就是查找到1)然后将mid = 1和3比较,此时mid < 3,所以会进入{2, 3}

仍然是mid =(r+l) / 2 ,最后就找到了元素3。

三.代码

下面用c++代码实现

#include<iostream>
using namespace std;
//使用模板函数
template <typename T >
//将索引为target的元素arr[target]
int BinraySearch(T arr[], int n, int target){
    int l = 0;
    int r = n - 1;
    while(l<=r) {
        //int mid = (l+r)/2;一分为二,但是这里可能存在溢出,所以用下面的优化版本
        int mid = l - (l + r) / 2;
        if (arr[target] == arr[mid]) {
            return mid;
        }
        else if (arr[target] > arr[mid]) {
            r = mid + 1;
        }
        else  //arr[target] < arr[mid];
            l = mid - 1;
    }
  //如果查找元素不存在,则返回-1
    return -1;
}

本作品采用《CC 协议》,转载必须注明作者和本文链接
刻意学习
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
未填写
文章
118
粉丝
88
喜欢
173
收藏
245
排名:367
访问:2.6 万
私信
所有博文
社区赞助商