当前位置:首页 > 算法 > 正文内容

【二分】----基础用法

亿万年的星光5年前 (2021-01-28)算法2439
0.二分法简介
  • 二分法是一种查找算法

  • 要求:数据必须是有序序列

  • 核心思想:掐头去尾取中间


1. 引入

对于一个有序数组,如{1,3,6,8,23,56,78,99},如果我们要查找其中的一个数78的下标位置,按照以前的写法,可能会这么写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
    int a[]={1,3,6,8,23,56,78,99},target;// 定义数组和要查找的目标
    int len= sizeof(a)/sizeof(int);
    cin>>target;
    for(int i=0;i<len;i++)
    {
        if(a[i]==target)
            {
                cout<<i<<endl;
                return 0;
            }
    }
    return 0;
}

这种顺序查找的方式对于数据量较小的情况还可以应付,但是对于数据量大的情况就很难处理了。试想一下特殊情况,如果你要查找的值正好在数组的最后一个,那么你的时间复杂度就是O(n)。所以引入二分查找来解决这个问题。


640?


640?


2. 二分法求解

【例题1】

【题目描述】

给定一个排序的整数数组(升序)和一个要查找的整数target,找到target第一次出现的下标(从0开始),如果target不存在于数组中,返回-1

【输入描述】

输入包含三行,第一行n,表示有n个数,第二行是已经排好序的n个数,第三行是target。

【输出描述】

一行,target第一次出现的下标,如果没有找到输出-1。

【样例输入1】

6
1 4 6 7 9 11
4


【样例输出1】

1

【样例输入2】

7
1 2 6 8 9 12 78
4

【样例输出2】

-1


【注意】题目不一定有解,可以遵循下面的算法框架

1
2
3
4
5
6
7
8
9
10
11
while (left < right - 1) {
    int mid = left + (right - left) / 2;
    //添加结束条件
     
    //
    if (A[mid] > A[left]) {
        left = mid;
    } else {
        right = 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
25
26
27
28
29
30
31
32
33
#include<cstdio>
#include<iostream>
using namespace std;
int search(int A[], int n, int target) 
    int left = 0, right = n-1; 
    while(left <= right) 
    
        // 注意:若使用(low+high)/2求中间位置容易溢出 
        int mid = left+((right-left)>>1);  
        if(A[mid] == target) 
            return mid; 
        else if(A[mid] < target) 
            left = mid+1; 
        else // A[mid] > target 
            right = mid-1; 
    
    return -1; 
int main()
{
    int a[100]={0},target;// 定义数组和要查找的目标
    int len,n,index;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];   
    }  
    cin>>target;
    index = search(a,n,target);
    cout<<index;
    return 0;
}



【例题2】

【题目描述】

给定一个有序(非降序)数组A,可含有重复元素,求最大的i使得A[i]等于target,不存在则返回-1。

【输入描述】

输入包含三行,第一行n,表示有n个数,第二行是已经排好序的n个数。

【输出描述】

一行,target最后一次出现的下标,如果没有找到输出-1。



扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

【贪心】区间调度

【贪心】区间调度

【题目描述】有n项工作,每项工作分别在si时间开始,在ti时间结束。对于每项工作,你都可以选择参与与否。如果选择了参与,那么自始至终都必须全程参与。此外,参与工作的时间段不能重叠(即使是开始与结束的瞬...

【分治】----快速幂

【分治】----快速幂

1.幂幂(power)是指乘方运算的结果。n^m指该式意义为m个n相乘。把n^m看作乘方的结果,叫做n的m次幂,也叫n的m次方。2.幂的数学表示和规则2^3  *   2...

【贪心】----排队打水

【贪心】----排队打水

一、基础版排队打水【题目描述】学校里有一个水房,水房里一共装有m 个龙头可供同学们打开水,每个龙头每秒钟的供水量相等,均为1。现在有n 名同学准备接水,他们的初始接水顺序已经确定。...

【贪心】区间覆盖

【贪心】区间覆盖

【题目描述】给定一个长度为m的区间,再给出n条线段的起点和终点(本题考虑闭区间),求最少使用多少线段可以将整个区间完全覆盖。【输入】第一行是区间长度m。第二行是n,表示有n个可选区间。后面跟着n行数据...

【贪心】----最优装载、背包、乘船问题

【贪心】----最优装载、背包、乘船问题

1.最优装载题目描述:有n个物体,第i个物体的重量为wi(wi为正整数)。选择尽量多的物体,使得总重量不超过C。【分析】由于只关心选择的物品的最大数量(而不是最大重量,最大重量需要考虑DP),所以装重...

【算法】二叉树(1):二叉树及其编号

【算法】二叉树(1):二叉树及其编号

0.前言        二叉树(Binary Tree)的递归定义如下:二叉树要么为空,要么由根结点(root)、左子树(left...