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

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

文章目录

【经典排序算法】二分查找法 (动图演示 + 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; i<n; ++i){if(arr[i] == key)//如果指定元素key与数组中的某元素arr[i]相等，则返回它的下标ireturn i;}return -1;//否则返回-1，表示未查找到与它相等的元素}//二分法查找指定元素所在位置（前提条件是先按从小到大进行排列）int BinarySearch1(int arr[], int size, int key) {int low = 0; //设置低下标int high = size-1; //设置高下标int mid;while(low <= high) //一旦高下标小于低下标结束while循环{mid = low+(high-low)>>1;//设置中间下标if(key < arr[mid]) //如果指定元素比中间下标的值小high = mid-1; //则把中间下标-1给高下标else 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 <= high;--> 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 < high) //一旦高下标小于低下标结束while循环{mid = low+(high-low)>>1;//设置中间下标if(key < arr[mid]) //如果指定元素比中间下标的值小high = mid; //则把中间下标-1给高下标else if(key > arr[mid])//如果指定元素比中间下标的值大low = mid+1; //则把中间下标+1给低下标else//否则返回 中间下标return mid;}return -1;//返回-1则表示在该数组中未找到该指定元素}

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

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

其示意图如下图所示：