二分查找——我欲修仙(功法篇)

一时失言乱红尘 2024-04-11 13:23 111阅读 0赞

> 个人主页：[【?个人主页】][Link 1]  
> 系列专栏：[【❤️我欲修仙】][Link 2]  
> 学习名言：临渊羡鱼,不如退而结网——《汉书董仲舒传》

## 系列文章目录 ##

第一章 ❤️ [二分查找][Link 3]

--------------------

#### 文章目录 ####

*  系列文章目录
 *  前言???
 *  二分查找？
 *  第一阶段 二分查找？???
 *  第二阶段 易错点???
 *   *  问题一：
     *  问题二
     *  总结
 *  题目代码（C语言实现）

--------------------

## 前言??? ##

经历了一段时间的《数据结构与算法》学习，你已经从凡人步入了修仙界，现在你可以尝试去接触一些简单的算法题开始你的修仙生涯了，那今天我们来看看今天的修炼吧⛽⛽⛽  
![力扣\# 704][704]

> 这是是一道非常经典的入门级修炼功法，收录在力扣\# 704，而它的名字就已经将写法写在你的脸上了?——二分查找  
> ps:工欲善其事必先利其器，一部好的功法可以让你在修仙路上少走许多弯路。???

## 二分查找？ ##

> 二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好，占用系统内存较少;其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功;否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

![在这里插入图片描述][151edbd5080f44769a50e6b648525926.gif_pic_center]

## 第一阶段 二分查找？??? ##

> 二分查找的基本思想是将n个元素分成大致相等的两部分，取a\[n/2\]与x做比较，如果x=a\[n/2\],则找到x,算法中止;如果x<a\[n/2\],则只要在数组a的左半部分继续搜索x,如果x>a\[n/2\],则只要在数组a的右半部搜索x.  
> 因此我们需要left变量middle变量，right变量以及以各target变量

在这个阶段我们需要了解二分查找的基本运算方式，以及需要使用的变量。

## 第二阶段 易错点??? ##

我们应该了解下二分算法的易错点

> 1.在循环体的跳出判定条件是左边大于等于右边（left>=right）还是左边大于右边（left>right）  
> 2.如果(str\[middle\]>target)，那么接下来我们应该将（middle）更新为（right）还是（right-1）?

### 问题一： ###

> 对待该问题我们需要首先将题意理解清楚，我们根据查找区间分为两种写法——左闭右闭写法和左必右开写法  
> 左闭右闭写法故名思意在该区间我们两头的数都应该取到，我们假设一个这样的区间\[1,1\]，很明显我们的判定条件上必须加上等于，与之相反的当区间为\[1,1)左闭右开时我们不能加上等于号。

### 问题二 ###

> 应对第二个问题我们只需简单的假设一下当我们使用左闭右闭写法时我们已经判断了(str\[middle\]>target)那么我们下一次判断的时候就不用该将（middle）加入进去那么自然我们会将（right）更新为（middle-1），当我们使用左闭右开写法时本来定义中就已经不包含（middle）值，那么我们为啥还要将（right）更新为（middle-1）呢？

### 总结 ###

> 简单总结一下：  
> 左闭右闭写法——要等于号，并且（middle）应更新为（left=right+1）或（right=middle-1）  
> 左闭右开写法——不要等于号，并且（middle）应更新为（right=middle和(left=middle+1)(这个地方要好好理解下哟)

## 题目代码（C语言实现） ##

#include<stdio.h>
    #include<string.h>
    #define MAX 100000
    int search(int* nums, int numsSize, int target)
    {
        
    	int left=0, right, middle;
    	right = numsSize;
    	while (left <= right)//这里是左闭右闭写法
    	{
        
    		middle = (left + right) / 2;
    		if (*(nums + middle) > target)
    			right = middle - 1;
    		else if (*(nums + middle) < target)
    			left = middle + 1;
    		else
    			return middle;
    	}
    	return -1;//查找失败，无该目标值
    }
    int main()
    {
        
    	int nums[MAX] = {
         0 };
    	int target = 0;
    	int numsSize = 0, i;
    	scanf("%d", &numsSize);//输入区间长度
    	printf("\n");
    	for (i = 0;i < numsSize;i++)
    		scanf("%d", nums + i);//输入查找区间
    	printf("\n");
    	scanf("%d", &target);//输入目标值
    	numsSize = strlen(nums);
    	printf("下标为：%d", search(nums,numsSize,target));
    
    }

[Link 1]: https://blog.csdn.net/weixin_73602725?type=blog
[Link 2]: https://blog.csdn.net/weixin_73602725/category_12259807.html?spm=1001.2014.3001.5482
[Link 3]: https://blog.csdn.net/weixin_73602725/article/details/129406349
[704]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/27870fc5530b46f2b42f2038ba7a0e23.png
[151edbd5080f44769a50e6b648525926.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/e0c53b6205834709a791ed6ebf98fcd3.gif