二分查找就该这样学
小禹禹，你们好呀！从今天开始景禹就要开始给大家分享查找和排序算法，有没有很鸡冻。查找算法在日常的考试、面试中都极为常见。
基础
静态查找（Static Search）：数据集合稳定，不需要添加，删除元素的查找操作。
动态查找（Dynamic Search）：在数据集合中进行查找的过程中，需要同时添加或删除元素的查找操作。
关键字（key）：数据元素（或记录）中某个数据项的值，用它可以唯一的标识（识别）一个数据元素（或记录）。
对于静态查找来说，我们可以采用用线性表结构组织数据，这样可以使用顺序查找算法，如果我们再对关键字进行排序，则可以使用折半查找算法或斐波那契查找算法等来提高查找的效率。
对于动态查找来说，我们则可以考虑使用二叉排序树的查找技术，另外我们还可以使用散列表结构来解决一些查找问题，这些查找算法景禹都会一点儿一点儿介绍给小禹禹的。
其实本质上查找算法一般分为两类：
顺序查找（Sequential Search）：将顺序遍历链表或数组，并检查每个元素。（比如线性查找） 区间查找（Interval Search）：这类算法是专门为查找排序的数据结构而设计的。这些类型的查找算法比线性查找有效得多，因为它们反复检查查找空间的中心并不断将查找空间缩减。（比如二分查找）
景禹今天主要给小禹禹分享一下线性查找和二分查找，其中线性查找的的思想简单，景禹就不一步一步给大家分析演示了，不过提供了动画演示，不理解的小禹禹可以对照着看一下。
线性查找
顺序查找（Sequential Search）又叫线性查找（Linear Search），是最基本的查找技术，它的查找过程为：从表中的第一个（或者最后一个）记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功。如果查找了所有的记录仍然找不到与给定值相等的关键字，则查找不成功。
动画演示
实现代码
从前往后进行遍历查找：
#include <stdio.h>
int search(int arr[], int n, int x)
{
int i;
for (i = 0; i < n; i++)
if (arr[i] == x)
return i;
return -1;
}
int main(void)
{
int arr[] = { 5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92 };
int x = 64;
int n = sizeof(arr) / sizeof(arr[0]);
int result = search(arr, n, x);
(result == -1) ? printf("Element is not present in array")
: printf("Element is present at index %d",
result);
return 0;
}从后往前进行遍历查找：
int search(int arr[], int n, int x)
{
int i = n-1;
while(arr[i] != x){
i--;
}
if(i >= 0)
return i;
return -1;
}时间复杂度
线性查找的时间复杂度为
二分查找
二分查找又叫做折半查找，其查找过程为：先确定待查记录所在的范围（区间），然后逐步缩小范围知道找到或者找不到该记录为止。注意二分查找是在有序表上进行的，且二分查找也是分治思想的很好例证。之前景禹在谈递归与分治时就曾介绍过二分查找，今日再详细探讨一下。
第一步：设置一个指向有序数组第一个元素 5 的low指针，和一个指向有序数组的最后一个元素 92 的high指针。
第三步：将给定值21与mid指针指向的值56进行比较，21 < 56，说明待查找元素21若存在，必在区间 [low,mid-1] 的范围内，则令 high = mid - 1 = 5- 1 = 4.
第四步：重新计算 mid 的值，mid =⌊(0+4)/2⌋=2.
第五步：将给定值21与mid指向的值19进行比较，21 > 19，说明待查找元素21若存在，必在区间 [mid+1,high] 的范围内，则令 low = mid + 1 = 2+ 1 = 3.
第六步：重新计算mid 的值，mid =⌊(3+4)/2⌋=3.
第七步：将给定值21与mid指向的值21进行比较，发现相等，查找成功。
从上面的例子可见，折半查找过程以处于区间中间位置mid记录的值和给定值比较，若相等，则查找成功，若不相等，则缩小范围，直至新的区间中间位置mid记录的值等于给定值或者查找区间的大小小于零时（表示查找不成功）为止。
二分查找递归实现
#include <stdio.h>
int binarySearch(int arr[], int low, int high, int x)
{
if (high >= low) {
int mid = low + (high - low) / 2;
//判断mid指向值是否等于指定值x
if (arr[mid] == x)
return mid;
//如果mid指向的元素的值大于指定值x，
//则递归地遍历区间[l,mid-1]
if (arr[mid] > x)
return binarySearch(arr, low, mid - 1, x);
//如果mid指向的元素的值小于指定值x，
//则递归地遍历区间[mid+1, high]
return binarySearch(arr, mid + 1, high, x);
}
//查找的元素不存在返回-1
return -1;
}
int main(void)
{
int arr[] = { 5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 64;
int result = binarySearch(arr, 0, n - 1, x);
(result == -1) ? printf("Element is not present in array")
: printf("Element is present at index %d",
result);
return 0;
}二分查找迭代实现
int binarySearch(int arr[], int low, int high, int x)
{
while(low <= high){
int mid = low + (high - low) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] < x){
low = mid + 1;
}
else{
high = mid - 1;
}
}
return -1;
}时间复杂度
为了清晰地计算二分查找的时间复杂度，我们将例子中的数组转化为一颗二叉树。
查找21仅需要比较2次，查找37仅需要比较3次。显而易见，对于一个有序数组而言，查找某个元素的判断次数最多也就是上面的一颗判断树的深度，而具有n个结点的判定树的深度为 ，所以在一个有序数组中查找一个元素的时间复杂度为 级别。
二分查找的应用
LeetCode 704. 二分查找 (Binary Search)
小禹禹赶紧去力扣提交一下，体验一波成功感吧，哈哈！！！景禹为了让小禹禹对二分查找理解更深刻，我们再来看一道题目。
题目描述
统计一个数字在排序数组中出现的次数。
例如输入排序数组[1, 2, 3, 3, 3, 3, 4, 5]和数字3，由于3在这个数组中出现了4次，因此输出4。
示例
示例 1：
输入：[1, 2, 3, 3, 3, 3, 4, 5] , 3
输出：4 解释：数组中总共有4个3
题解：
第一种方式当然特别简单，只需要写一个循环，遍历数组一遍，统计出排序数组中重复数字的个数。时间复杂度为 .
另一种方式就是我们今天所学习的二分查找了，怎么办？
小禹禹：嗯？？？还可以用二分查找，也就意味着时间复杂度降到 .
景禹：的确如此，那就让我们快乐的开始吧。
首先我们应该注意到输入的是一个 排序数组 ，面试只要提到有序数组这种，小禹禹一定要有警惕性，面试官可不想只看到 的解法。
二分查找本身是用于查找数组中是否存在一个元素，若存在在返回数组的下标，若不存在，则返回-1。而现在我们我们要统计的是数组中重复元素出现的次数，有没有可能对二分查找进行修改后做到呢？答案是肯定的。
我们只需要确定出第一个3的位置以及最后一个3的位置，然后将两个位置相减并加一，就是重复元素的个数。
如何计算第一个重复元素的位置？
第一步：依然是设置一个指向第一个元素的low指针，和指向最后一个元素的high指针
第二步：计算指针 mid =⌊(0+7)/2⌋=3.
high = mid - 1. 否则，令 low = mid + 1 . 这里是是大于等于，故 high = 3 - 1 = 2.
第四步：计算指针 mid =⌊(0+2)/2⌋=1.
第五步：比较mid 指向的元素 2 与重复元素 3 的大小， 2 < 3，则 low = mid + 1 = 2
第六步：计算 mid =⌊(2+2)/2⌋=2.
第七步：比较mid 指向的元素 3 与重复元素 3 的大小， 3 <= 3，则 high = mid - 1 = 1 此时 low > high ,退出循环并返回指针 low 的值 2。
如何获得最后一个重复元素的位置？
与上面寻找第一个重复元素的位置一样，我们只需要将判断条件进行更改，也就是说，当mid指向的值 小于等于 重复元素，则 low = mid + 1 ，否则，令 high = mid - 1 .
通俗来讲，我们寻找第一个重复元素，将high指针向low 靠近，寻找最后一个元素，将low指针向high靠近。
我们一起来看代码吧！超级简单。
计算第一个重复元素的位置：
int binarySearch_start(int arr[], int low, int high, int x)
{
while(low <= high){
int mid = low + (high - low) / 2;
if (arr[mid] < x){
low = mid + 1;
}
else{
high = mid - 1;
}
}
return low;
}计算最后一个重复元素的位置：
int binarySearch_end(int arr[], int low, int high, int x)
{
while(low <= high){
int mid = low + (high - low) / 2;
if (arr[mid] <= x){
low = mid + 1;
}
else{
high = mid - 1;
}
}
return low;
}至于重复元素的个数则为：最后一个重复元素的位置 - 最后一个重复元素的位置 + 1.
当然我们可以有一种更简洁的思路，那就是找到第一个元素的位置，然后找出最后一个元素的位置的下一个位置，然后进行相减即可得到重复元素的个数：
#include <stdio.h>
int binarySearch(int arr[], int low, int high, int x)
{
while(low <= high){
int mid = low + (high - low) / 2;
if (arr[mid] < x){
low = mid + 1;
}
else{
high = mid - 1;
}
}
return low;
}
int main(void)
{
int arr[] = { 1,2,3,4,4,4,4,4,4,4,6,6,7,8,9,10 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 4;
int start = binarySearch(arr, 0, n - 1, x);
int end = binarySearch(arr, 0, n -1 ,x+1);
int result = end - start;
printf("The number of Repeating element is %d",result);
return 0;
}景禹今天就写到这里啦，希望小禹禹有所收获，一切顺利，学习愉快，原创不易，素质三连是对景禹的最大鼓励！一起加油呀~~
作者：景禹，一个追求极致的共享主义者，想带你一起拥有更美好的生活，化作你的一把伞。