欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法笔记——二分查找法

程序员文章站 2023-12-22 13:45:52
...

二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。
二分查找的基本思想是将n个元素分成大致相等的两部分,取a[n/2]与x做比较,如果x=a[n/2],则找到x,算法中止;如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x。

题目:

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。

用C语言代码实现如下:

1、遍历法

int searchInsert(int* nums, int numsSize, int target)
{
    int i;
    for (i = 0; i < numsSize; i++)
    {
        if (nums[i] >= target)
            return i;
    }
    return i;
}

2、二分查找法

int searchInsert(int* nums, int numsSize, int target)
{
    int l=0,r=numsSize-1,m;
    while(l<=r)
    {
        m=(l+r)/2;
        if(nums[m]==target)
            return m;
        else if(nums[m]>target)
            r=m-1;
        else 
            l=m+1;
    }
    return l;
}

上一篇:

下一篇: