【经典排序算法】二分查找法 (动图演示 + C 语言代码实现)

您所在的位置：网站首页 › 二分法讲课视频 › 【经典排序算法】二分查找法 (动图演示 + C 语言代码实现)

【经典排序算法】二分查找法 (动图演示 + C 语言代码实现)

2024-07-14 07:39| 来源: 网络整理| 查看: 265

👩‍💻 👉 【经典排序算法】十大经典排序算法汇总篇

文章目录【经典排序算法】二分查找法 (动图演示 + C 语言代码实现)1、动图演示2、查找场景3、查找条件4、代码实现（C语言）5、注意事项5.1 Binary Search 15.2 Binary Search 2

1、动图演示

首先看一下二分查找与顺序查找的对比。在这里插入图片描述可以看出 binary search 在查找数字 37 时只需3次，而 sequential search 查找37时需要11次。

由下图可以看出二分查找的前提条件是有序序列。

在这里插入图片描述

2、查找场景

二分搜索用于在一个单调或者局部单调有序数组中查找一个符合某些条件的值，时间复杂度为O(logN)

3、查找条件

二分查找的前提条件是有序数列，普通查找则不需要。查找到返回该元素的下标，否则返回-1。普通查找的时间复杂度为O(N), 二分查找的时间复杂度为O(logN)。 N/2/2···/2=1，2^m=N(m为折半查找的次数)，那么m=log(N)，二分查找的时间复杂度就为O(logN)。

4、代码实现（C语言） int Find(int arr[], int n, int key) //查找指定元素所在位置 { for(int i=0; i1; //设置中间下标 if(key arr[mid]) //如果指定元素比中间下标的值大 low = mid+1; //则把中间下标+1给低下标 else //否则返回中间下标 return mid; } return -1; //返回-1则表示在该数组中未找到该指定元素 } 5、注意事项 5.1 Binary Search 1

上述 Binary Search 1函数注意以下5个点：

--> low=0; high=size-1;// [] 闭区间，high为最后一个元素的下标 --> low mid= low+(high-low)>>1; --> high=mid-1; --> low=mid+1;

其示意图如下图所示：在这里插入图片描述

5.2 Binary Search 2 int BinarySearch2(int arr[], int size, int key) { int low = 0; //设置低下标 int high = size; //设置高下标 int mid; while(low >1; //设置中间下标 if(key arr[mid]) //如果指定元素比中间下标的值大 low = mid+1; //则把中间下标+1给低下标 else //否则返回中间下标 return mid; } return -1; //返回-1则表示在该数组中未找到该指定元素 }

那么Binary Search 2注意以下5个点：

--> low=0;high=size;// [ ）左闭右开，high为最后一个元素的下一个位置 --> low mid= low+(high-low)>>1; --> high=mid; --> low=mid+1;

其示意图如下图所示：在这里插入图片描述

【本文地址】

【经典排序算法】二分查找法 (动图演示 + C 语言代码实现)

【经典排序算法】二分查找法 (动图演示 + C 语言代码实现)

今日新闻

推荐新闻