青少年编程知识记录 - 【二分】----基础用法

2021年01月28日 16:00:26

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

0.二分法简介

二分法是一种查找算法
要求：数据必须是有序序列
核心思想：掐头去尾取中间

1. 引入

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

#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)。所以引入二分查找来解决这个问题。

2. 二分法求解

【例题1】

【题目描述】

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

【输入描述】

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

【输出描述】

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

【样例输入1】

6  1 4 6 7 9 11  4

【样例输出1】

【样例输入2】

7  1 2 6 8 9 12 78  4

【样例输出2】

-1

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

while (left < right - 1) {
    int mid = left + (right - left) / 2;
    //添加结束条件 
        // 
    if (A[mid] > A[left]) {
        left = mid;
    } else {
        right = mid;
    }
}

【参考代码】

#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。