首页 > 其他分享 >力扣二分查找

力扣二分查找

时间:2022-12-30 10:36:56浏览次数:60  
标签:二分 下标 target nums int 力扣 查找 目标值 return

题目

给定一个 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

提示:

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/binary-search
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

二分算法的步骤有
1.确定目标值
2.确定目标范围,并确定初始范围最小值和初始范围最大值
3.确定判断条件,什么情况下要增加范围最小值,什么情况下要增加范围最大值?
本题的话,就是当目标值比范围中值要大的时候,2.4.8,6>4,所以此时要增加范围最小值,反之减小最大值
4.边界条件
4.1找到了目标值,可以定义一个具有特殊意义的变量,如 int x,赋值为0则为没找到,反之就是找到了,然后因为本题是要输出下标,所以得再弄个变量存储下标,如果找到了目标值的话,就输出存储的下标。
4.2没找到目标值,没找到下标的话,得分两种情况。1是没找完,2是找完了但找不到。
没找完的话,就通过判断条件,缩小范围再找一次就行
如果是找完了但没找到。那首先是怎么才算找完了,其次是返回没找到的值。
如果范围最小值>=最大值了,那就说明每一个都找过了,然后就可以返回特殊值,告诉函数他找不到了

代码

点击查看代码
int search(int* nums, int numsSize, int target){
int previous=0,end=numsSize-1;
int compare(int xiabiao)
{
    if(nums[xiabiao]==target)
    {
        return xiabiao;
    }
    else if(previous>end)
    {
        return -1;
    }
    else if(target>nums[xiabiao])
    {
        previous=xiabiao+1;
    }
    else
    {
        end=xiabiao-1;
    }
    int jieshu=compare((previous+end)/2);
    if(jieshu!=-1)
    {
        return jieshu;
    }
    return -1;
}
int jieshu = compare((previous+end)/2);
if(jieshu!=-1)
    {
        return jieshu;
    }
    return -1;
}

现场思路

//查找中间元素是否等于目标值,如果是,那就返回下标,否则判断中间元素跟目标值的大小比较
//然后对其区间做进一步缩减,直到范围起点跟范围终点发生了越界,就判断不存在目标值

标签:二分,下标,target,nums,int,力扣,查找,目标值,return
From: https://www.cnblogs.com/aduiduidui/p/17014215.html

相关文章

  • 二分查找
    题目题目地址描述请实现无重复数字的升序数组的二分查找给定一个元素升序的、无重复数字的整型数组nums和一个目标值target,写一个函数搜索nums中的target,如果......
  • 【LeeCode】34. 在排序数组中查找元素的第一个和最后一个位置
    【题目描述】给你一个按照非递减顺序排列的整数数组 ​​nums​​​,和一个目标值 ​​target​​。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目......
  • 【LeetCode数组#1二分查找】二分查找、搜索插入、在排序数组中查找元素的第一个和最后
    二分查找题目力扣704题目链接给定一个n个元素有序的(升序)整型数组nums和一个目标值target,写一个函数搜索nums中的target,如果目标值存在返回下标,否则返回-1。......
  • 二分搜索与二分答案
    二分的本质序列要满足有序性或者有有序的性质:有单调性一定可以二分,没有单调性也可以进行二分;下面是两个模板;tips:mid=男左女右,男加1boolcheck(intx){/*...*/}//......
  • 二分算法
    二分算法题目合集题目来源难度袋子里数目最少的球力扣中等礼盒的最大甜蜜度力扣中等两球之间的磁力力扣中等机器人跳跃问题Acwing中等分......
  • 查找蓝牙WiFi功能,搜索名字并列举出来
    先有一个概念,蓝牙分为普通蓝牙和低功耗(BLE)蓝牙,低功耗蓝牙激活时信号和普通蓝牙信号一样,低功耗时必须搜索低功耗蓝牙信号如果使用普通代码搜索,不能搜索到低功耗蓝牙信号......
  • windows 根据父进程pid查找所有子进程id(C++)
    直接上代码:大家直接调用即可#include<iostream>#include<Windows.h>#include<tlhelp32.h>#include<string>#include<vector>usingnamespacestd;vector<DWORD>GetPro......
  • (转载)Windows 查找占用串口(COM)的进程
    原文地址:Windows查找占用串口(COM)的进程_weixin_42501466的博客-CSDN博客_如何查看串口被哪个程序占用查找占用串口的进程1、Win+R打开运行窗口2、输入regedi......
  • pytorch:二分类时的loss选择
    PyTorch二分类时BCELoss,CrossEntropyLoss,Sigmoid等的选择和使用这里就总结一下使用PyTorch做二分类时的几种情况:总体上来讲,有三种实现形式:最后分类层降至一维,使用sigmo......
  • vba-多列同时查找满足条件的行号
    我首先想到的非环版本要做到这一点(循环简单得多),是使用匹配(),但如果你有多个值使用A=Q或同日在那里,你可能会遇到一个问题。Dimi,jasIntegeri=Application.Match(RefC......