二分法

admin
admin
admin
138635
文章
114
评论
2022年1月6日01:36:10评论47 views字数 1027阅读3分25秒阅读模式

概念

二分法查找，也称为折半法，是一种在有序数组中查找特定元素的搜索算法。

思路

二分法查找的思路如下：

（1）首先，从数组的中间元素开始搜索，如果该元素正好是目标元素，则搜索过程结束，否则执行下一步。

（2）如果目标元素大于/小于中间元素，则在数组大于/小于中间元素的那一半区域查找，然后重复步骤（1）的操作。

（3）如果某一步数组为空，则表示找不到目标元素。

二分法查找的时间复杂度O(logn)。

框架

非递归方法:

区间问题

二分查找，要注意的地方

闭区间 [L,R]:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
int binary_search(int a[],int size,int p)
{
    int L = 0;
    int R = size - 1;
    while(L <= R)        //查找区间，以两个数据为例子，L,R 都完成比较
    {
        int mid = L + (R - L)/2;
        if(p == a[mid])
            return mid;
        else if(p > a[mid]){
            L = mid +1;
        }
        else{
            R = mid - 1;
        }
    }
}

左闭右开 [L,R)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
int binary_search(int a[],int size,int p)
{
    int L = 0;
    int R = size - 1;
    while(L < R)
    {
        int mid = L + (R -L)/2;
        if(p == a[mid])
            return mid;
        else if(p < a[mid]){
            R = mid;
        }
        else{
            L = mid;
        }
    }
}

左开右开 (L ,R):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
int binary_search(int a[],int size,int p)
{
    int L = 0;
    int R = size - 1;
    while(R-L > 1){
        int mid = L + (R-L)/2;
        if(a[mid] == p)
            return mid;
        else if(p < a[mid]){
            R = mid;
        }
        else{
            L = mid;
        }
    }
}

例题

  1. 求开方
  2. 大于给定元素的最小元素
  3. 有序数组的 Single Element
  4. 第一个错误的版本
  5. 旋转数组的最小数字
  6. 查找区间

https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.md

参考文章:

算法-二分查找

二分查找，要注意的地方

FROM :blog.cfyqy.com | Author:cfyqy

免责声明:文章中涉及的程序(方法)可能带有攻击性，仅供安全研究与教学之用，读者将其信息做其他用途，由读者承担全部法律及连带责任，本站不承担任何法律及连带责任；如有问题可邮件联系(建议使用企业邮箱或有效邮箱,避免邮件被拦截，联系方式见首页)，望知悉。
  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年1月6日01:36:10
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出)：
                   二分法https://cn-sec.com/archives/721954.html
                  免责声明:文章中涉及的程序(方法)可能带有攻击性，仅供安全研究与教学之用，读者将其信息做其他用途，由读者承担全部法律及连带责任，本站不承担任何法律及连带责任；如有问题可邮件联系(建议使用企业邮箱或有效邮箱,避免邮件被拦截，联系方式见首页)，望知悉.

发表评论

匿名网友 填写信息