算法-二分查找
二分查找
704 二分查找
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
int search(int* nums, int numsSize, int target){
//用middle表示low、high中间的数
int middle=0;
//find表示在数组中找到目标值
int find=0;
//用两个指针分别指向数组的开头、结尾
int low=0,high=numsSize-1;
while(low<=high)
{
middle=(low+high)/2;
if(nums[middle]==target)
{
find=1;
break;
}
else if(nums[middle]
35 搜索插入位置
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
输入: nums = [1,3,5,6], target = 5
输出: 2
输入: nums = [1,3,5,6], target = 2
输出: 1
int searchInsert(int* nums, int numsSize, int target){
int low=0,high=numsSize-1;
int mid=0;
while(low<=high)
{
mid=low+(high-low)/2;
if(nums[mid]==target)
{
low=mid;
break;
}
else if(nums[mid]>target)
high=mid-1;
else
low=mid+1;
}
return low;
}