算法笔记——二分查找法
程序员文章站
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;
}