C语言详细讲解二分查找用法

目录

【力扣题号】704.二分查找 力扣题目链接

示例 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]之间。

注意读题，数组为有序数组，且数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的。

在二分查找的过程中，保持不变量，就是在 while 寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。

写二分法，区间的定义一般为两种，左闭右闭即 [left, right]，或者左闭右开即 [left, right)。

  • 二分法第一种写法

第一种写法，我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right] 。因为定义 target 在 [left, right] 区间，所以有如下两点：

while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=

if (nums[middle] > target) ，right 要赋值为 middle - 1，因为当前这个 nums[middle] 一定不是 target ，那么接下来要查找的左区间结束下标位置就是 middle - 1

// 版本一
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
        while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
            int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
            if (nums[middle] > target) {
                right = middle - 1; // target 在左区间，所以[left, middle - 1]
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，所以[middle + 1, right]
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};
  • 二分法第二种写法

如果说定义 target 是在一个在左闭右开的区间里，也就是[left, right) ，那么二分法的边界处理方式则截然不同。

有如下两点：

while (left < right)，这里使用 < ,因为 left == right 在区间 [left, right) 是没有意义的

if (nums[middle] > target) ，right 更新为 middle，因为当前 nums[middle] 不等于 target，去左区间继续寻找，而寻找区间是左闭右开区间，所以 right 更新为 middle，即：下一个查询区间不会去比较 nums[middle]

// 版本二
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)
        while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                right = middle; // target 在左区间，在[left, middle)中
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，在[middle + 1, right)中
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

通过以上两种方法，要注意它们不同的地方：

① right 的初始值不一样

② 左右区间的更新值的差别

参考：《代码随想录》

到此这篇关于C语言详细讲解二分查找用法的文章就介绍到这了,更多相关C语言 二分查找内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C语言算法--有序查找(折半查找/二分查找)

    目录 题目 解法一: 挨个遍历 方法二:折半查找/二分查找(仅适用于有序查找) 总结 题目 首先我们来把题目瞅一眼: 在一个有序数组中查找具体的某个数字n. 编写int binary_search (int x, int v[], int n); 功能:在v [0] <= v [1] <= v [2] <= -. <= v [n-1]的数组中查找x. 题目大概的意思就是说这是一串有序的数组,我们编写代码完成以下功能:如果输入的数字在数组中,就输出找到了并输出下标,如果输入的数字不在

  • C语言二分查找算法及实现代码

    C语言二分查找算法及实现代码

    二分査找也称折半査找,其优点是查找速度快,缺点是要求所要査找的数据必须是有序序列.该算法的基本思想是将所要査找的序列的中间位置的数据与所要査找的元素进行比较,如果相等,则表示査找成功,否则将以该位置为基准将所要査找的序列分为左右两部分.接下来根据所要査找序列的升降序规律及中间元素与所查找元素的大小关系,来选择所要査找元素可能存在的那部分序列,对其采用同样的方法进行査找,直至能够确定所要查找的元素是否存在,具体的使用方法可通过下面的代码具体了解. #include <stdio.h> binar

  • 用C语言实现二分查找算法

    用C语言实现二分查找算法

    目录 一.前言 二.二分查找法 1.什么是二分查找法 2.如何用c语言来实现二分查找法 三.总结 总结 一.前言 假如今天我们需要在一个有序的数组中来寻找一个数的下标,就用"1,2,3,4,5,6,7,8,9"这九个数组成的数组来说,假如我们想寻找'2',那很简单我们只用从小到大开始寻找,寻找两次就完成了,但是我们想寻找'7',我们继续用从小到大挨个寻找,这就显得有点慢并且耗时长还没有效率,因此我们可以有一种全新的方法,二分查找法来解决这个问题. 二.二分查找法 1.什么是二分查找法

  • C语言快速排序与二分查找算法示例

    本文实例讲述了C语言二分排序与查找算法.分享给大家供大家参考,具体如下: 题目:首先产生随机数,再进行快速排序,再进行二分查找. 实现代码: #include <stdio.h> #include <stdlib.h> #include <time.h> void quiksort(int a[],int low,int high) { int i = low; int j = high; int temp = a[i]; if( low < high) { wh

  • C语言详细讲解二分查找用法

    目录 [力扣题号]704.二分查找 力扣题目链接 示例 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的每个元素

  • C语言详细讲解指针数组的用法

    C语言详细讲解指针数组的用法

    目录 1. 指针数组定义方法 2. 指针的指针(二级指针) 3. 字符串和指针 4. 数组指针 定义方法 数组指针的用法 1. 指针数组定义方法 格式: 类型说明符 *数组名[ 元素个数 ] int *p[10]; // 定义了一个整型指针数组p,有10个元素,都是int *类型的变量 指针数组的分类: 同指针类型的分类,见上一篇 大多数情况下,指针数组都用来保存多个字符串. #include <stdio.h> int main() { char *name[5] = {"Hell

  • C语言详细讲解if语句与switch语句的用法

    C语言详细讲解if语句与switch语句的用法

    目录 一.if 语句 二.switch 语句 三.错误提示 一.if 语句 格式: if(写条件){输出内容}条件为真运行这个. else {输出内容}否则输出这个. 代码: #include <stdio.h> int main(void) { int score; //定义一个变量 score printf("请输入你的分数:"); scanf("%d",&score); //键盘输入你想要的分数 if (score>700) //给出

  • C语言详细讲解while语句的用法

    C语言详细讲解while语句的用法

    目录 while语句格式 例题1 例题2 例题3 while语句格式 格式: while(表达式){    语句块} 1.先执行while(表达式),如条件为真执行语句块: 2.执行完语句块,继续执行表达式: 3.知道表达式为假.就退出循环,执行while后面的代码. 例题1 用while语句,输出0-9的值. 代码: #include <stdio.h> int main (void) { int i=0; //初始条件i=0; while(i<10) //while 循环 //whi

  • C语言 详细讲解#pragma的使用方法

    C语言 详细讲解#pragma的使用方法

    目录 一.#pragma 简介 二.#pragma message 三.#pragma once 四.#pragma pack 五.小结 一.#pragma 简介 #pragma 用于指示编译器完成一些特定的动作 #pragma 所定义的很多指示字是编译器特有的 #pragma 在不同的编译器间是不可移植的 预处理器将忽略它不认识的 #pragma 指令 不同的编译器可能以不同的方式解释同一条 #pragma 指令 一般用法: #pragma parameter 注:不同的 parameter

  • C语言详细讲解#error与#line如何使用

    C语言详细讲解#error与#line如何使用

    目录 一.#error 的用法 二.#line 的用法 三.小结 一.#error 的用法 #error 用于生成一个编译错误消息 用法 #error message,message不需要用双引号包围 #error 编译指示字用于自定义程序员特有的编译错误消息,类似的,#warning 用于生成编译警告. #error 是一种预编译器指示字 #error 可用于提示编译条件是否满足 用法示例如下: 编译过程中的任意错误信息意味着无法生成最终的可执行程序. 下面初探一下 #error #inclu

  • C语言数据结构中二分查找递归非递归实现并分析

    C语言数据结构中二分查找递归非递归实现并分析

    C语言数据结构中二分查找递归非递归实现并分析 前言: 二分查找在有序数列的查找过程中算法复杂度低,并且效率很高.因此较为受我们追捧.其实二分查找算法,是一个很经典的算法.但是呢,又容易写错.因为总是考虑不全边界问题. 用非递归简单分析一下,在编写过程中,如果编写的是以下的代码: #include<iostream> #include<assert.h> using namespace std; int binaty_search(int* arr, size_t n, int x)

  • C语言基础之二分查找知识最全汇总

    C语言基础之二分查找知识最全汇总

    一.前言 在自学二分查找的过程中我想到了一些变化问题,有的自己就慢慢理解了,有的在网上找到了答案,奈何没有找到想要的总结归纳.我就斗胆自己写了一篇,号称史上最全.希望和我一样的伙伴可以少走一点弯路. 二分查找凭借其低时间复杂度O(log(n))成为了各个蒟蒻的入门知识,但是其衍生出的各种题目相较原题目而言就没有那么容易求解,以下借用c语言实现二分查找算法及其衍生.二分查找仅适用于事先已经排好序的顺序表.其基本思路就是每次取中间数,如果中间数大于所求数就向上查找,反之向下. 二.原始二分查找 1.

  • C语言巧用二分查找实现猜数游戏

    C语言巧用二分查找实现猜数游戏

    目录 (壹)二分查找   1.1  何为二分查找   1.2  二分查找的原理   1.3  查找条件   1.4  代码实现 1.4.1  初始化数据 1.4.2  核心函数 (贰)猜数字游戏   2.1  菜单初始化   2.2  核心函数   2.3  main函数   2.4  总代码 文章Gitee仓库:文章源代码 (壹)二分查找   1.1  何为二分查找 折半查找,也称二分查找,在某些情况下相比于顺序查找,使用折半查找算法的效率更高.但是该算法的使用的前提是静态查找表中的数据必须是

  • C语言 详细讲解逻辑运算符的使用

    C语言 详细讲解逻辑运算符的使用

    目录 一.&& 与 II 分析 二.!分析 三.小结 一.&& 与 II 分析 下面的程序运行结束后,i, j,k 的值分别为多少? #include <stdio.h> int main() { int i = 0; int j = 0; int k = 0; ++i || ++j && ++k; printf("i = %d\n", i); printf("j = %d\n", j); printf(&

随机推荐