二分查找
概念
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
二分查找有着惊人的查找速度 O(logn)
我们假设数据大小是n，每次查找后数据都会缩小为原来的一半。最坏情况下，直到查找区间被缩小为空才停止。
可以看出，这是一个等比数列。其中n/2k=1时，k的值就是总共缩小的次数。而每一次缩小操作只涉及两个数据大小的比较，所以，经过了k次区间的缩小操作，时间复杂度就是O(k)。我们可以求得k=logn，所以时间复杂度是O(logn)。
举个例子：我们在42亿个数据中超找一个数，用二分查找最多只需要比较32次（感觉不可思议吧）。
二分查找应用有什么局限性呢
首先二分查找依赖的是顺序表结构，简单点说就是数组
那二分查找是否可以依赖于其它的数据结构呢？ 比如链表。答案肯定是不可以的，主要是二分查找算法要按照下表随机访问元素。而链表的随机访问复杂度是O(n)。所以，如果数据使用链表存储，二分查找的时间复杂度就会很高。
二分查找只能用于在数据是通过顺序表来存储的数据结构上。并且已经是进行过排序的顺序结构。如果使用其它数据结构存储，则无法应用二分查找。
其次，二分查找针对的是有序的数据。
二分查找对这一点要求比较苛刻，数据必须是有序的。如果数据无序，我们首先就是需要进行排序。排序最低的时间复杂度是O(nlogn)。所以，我们针对的是一组静态的数据，没有过多的插入删除操作，我们可以进行一次排序，多次二分查找。这样排序的成本就会降低。
如果经常需要插入删除，那我们就要频繁的排序，这样维护有序的数据结构成本就非常高。
下面的代码是实现了一些常见的二分查找的题目。
此篇博客参考于王争老师的课
代码和思想是自己理解后的实现。
#include<iostream>
#include<array>
#include<memory>
class search
{
public:
int s1(int arr[], int len, int ser); //二分查找查找一个数
int s2(int arr[], int len, int ser); //二分查找 找出第一个值等于给定的元素
int s3(int arr[], int len, int ser);//查找最后一个值等于给定的元素
int s4(int arr[], int len, int ser);//查找第一个大于等于给定元素的值
int s5(int arr[], int len, int ser);//查找最后一个小于等于给定元素的值
};
int search::s1(int arr[], int len, int ser)
{
int low = 0;
int high = len - 1;
int mid;
while(low <= high)
{
mid = low + ((high - low) >> 1); //避免数字溢出int范围
if(arr[mid] == ser)
return mid;
else if(ser > arr[mid])
low = mid + 1;
else if(ser < arr[mid])
high = mid - 1;
}
return -1;
}
int search::s2(int arr[], int len, int ser)
{
int low = 0;
int high = len - 1;
int mid;
while(low <= high)
{
mid = low + ((high - low) >> 1);
if(arr[mid] > ser)
high = mid -1;
else if(arr[mid] < ser)
low = mid + 1;
else
{
if(mid == 0 || arr[mid - 1] != ser)
return mid;
else
high = mid -1;
}
}
}
int search::s3(int arr[], int len, int ser)
{
int low = 0;
int high = len - 1;
int mid;
while(low <= high)
{
mid = low + ((high - low) >> 1);
if(arr[mid] > ser)
high = mid - 1;
else if(arr[mid] < ser)
low = mid + 1;
else
{
if(mid == (len -1) || arr[mid + 1] != ser)
return mid;
else
low = mid + 1;
}
}
}
int search::s4(int arr[], int len, int ser)
{
int low = 0;
int high = len - 1;
int mid;
while(low <= high)
{
mid = low + ((high - low) >> 1);
if(arr[mid] < ser)
low = mid + 1;
else
{
if(mid == 0 || arr[mid - 1] < ser)
return mid;
else
{
high = mid - 1;
}
}
}
}
int search::s5(int arr[], int len, int ser)
{
int low = 0;
int high = len - 1;
int mid;
while(low <= high)
{
mid = low + ((high - low ) >> 1);
if(arr[mid] > ser)
high = mid -1;
else
{
if(mid == 0 || arr[mid + 1] >ser)
return mid;
else
low = mid + 1;
}
}
}
int main()
{
int arr[15] = {1, 3, 5, 5, 5, 6, 6, 9, 17, 21, 35, 36, 36, 49, 100};
search solution;
int result;
result = solution.s1(arr, 15, 17);
std::cout << "17 is in arr " << result << "\n";
result = solution.s2(arr, 15, 5);
std::cout << "first 5 is in arr " << result << std::endl;
result = solution.s3(arr, 15, 6);
std::cout << "last 6 is in arr" << result << std::endl;
result = solution.s4(arr, 15, 10);
std::cout << "the first big than 10 is " << result << "\n";
result = solution.s5(arr, 15, 6);
std::cout << "last small than 6 is " << result << "\n";
return 0;
}