二分查找/排序
一、前言
二分查找和排序是数据结构中重要的一个章节，他的重要性也不言而喻，在未来不管是笔试还是面试都会遇到这类的题目，所以接下来我就会把一些常考的题目全部整理出来供大家学习指正。
二、学习刷题网站
点击下面链接即可进行刷题学习
开始刷题
三、刷题
先说明一下一些题目取自牛客网面试必刷TOP101
里面的一些题目在我以前的文章详细写到过，如果没有用新的方法就不会再做讲解
【剑指Offer】二分法例题
<1>二分查找-I
题目链接
描述
请实现无重复数字的升序数组的二分查找
给定一个 元素升序的、无重复数字的整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标（下标从 0 开始），否则返回 -1
数据范围：0 ≤ len(nums) ≤ 2×10^5， 数组中任意值满足 ∣val∣≤10^9
进阶：时间复杂度O(logn) ，空间复杂度 O(1)
示例1
输入：[-1,0,3,4,6,10,13,14],13
返回值：6
说明：13 出现在nums中并且下标为 6
示例2
输入：[],3
返回值：-1
说明：nums为空，返回-1
示例3
输入：[-1,0,3,4,6,10,13,14],2
返回值：-1
说明：2 不存在nums中因此返回 -1
思路分析：
这道题很显然要用二分查找，每次都取中间的数据跟目标数据比较，以此来缩小区间，要注意left和right相等时也要比较。
intsearch(int* nums,int numsLen,int target ){int left =0, right = numsLen -1;while(left <= right){int mid =(left + right)>>1;if(nums[mid]< target){
left = mid +1;}elseif(nums[mid]> target){
right = mid -1;}else{return mid;}}return-1;}
<2>数组中的逆序对
题目链接
描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007
数据范围： 对于50% 的数据,size ≤ 10^4
对于100% 的数据, size ≤ 10^5
数组中所有数字的值满足 0 ≤ val ≤ 1000000
要求：空间复杂度O(n)，时间复杂度O(nlogn)
输入描述：
题目保证输入的数组中没有的相同的数字
示例1
输入：[1,2,3,4,5,6,7,0]
返回值：7
示例2
输入：[1,2,3]
返回值：0
思路分析：
首先因为复杂度的要求暴力求解行不通。那么我们就可以用归并法：
归并排序
归并排序的方法就不过多介绍，在我以前的文章里有详细介绍：八大排序，你都掌握了吗？
首先看一个问题：假设有两个区间
[4, 5]
和
[2, 3]
他的逆序对数为(4, 2), (4, 3), (5, 2), (5, 3)，如果不是有序的呢？
[5，4]
和
[3，2]
（同一区间已经计算过）结果还是4个，那么拍成有序有必要吗？
答案是有必要
可以看这样一个场景：
两个区间[4, 5]和
[2, 3]我们知道4 > 2，那么显然4 后面的数字都大于2，就可以方便我们计数。
voidmerge(int* data,int* tmp,int left,int right,long* k){if(left >= right){return;}int mid =(left + right)>>1;merge(data, tmp, left, mid, k);merge(data, tmp, mid +1, right, k);int begin1 = left, end1 = mid;int begin2 = mid +1, end2 = right;//放入tmp数组int i = left;while(begin1 <= end1 && begin2 <= end2){if(data[begin1]< data[begin2]){
tmp[i++]= data[begin1];
begin1++;}else{
tmp[i++]= data[begin2];(*k)+=(end1 - begin1 +1);
begin2++;}}while(begin1 <= end1){
tmp[i++]= data[begin1++];//(*k) += len;}while(begin2 <= end2){
tmp[i++]= data[begin2++];}//把tmp拷贝回去for(int j = left; j <= right; j++){
data[j]= tmp[j];}}intInversePairs(int* data,int dataLen ){int* tmp =(int*)malloc(sizeof(int)* dataLen);int left =0, right = dataLen -1;long k =0;merge(data, tmp, left, right,&k);return k %1000000007;}
<3>比较版本号
题目链接
描述
牛客项目发布项目版本时会有版本号，比如1.02.11，2.14.4等等
现在给你2个版本号version1和version2，请你比较他们的大小
版本号是由修订号组成，修订号与修订号之间由一个"."连接。1个修订号可能有多位数字组成，修订号可能包含前导0，且是合法的。例如，1.02.11，0.1，0.2都是合法的版本号
每个版本号至少包含1个修订号。
修订号从左到右编号，下标从0开始，最左边的修订号下标为0，下一个修订号下标为1，以此类推。
比较规则：
一. 比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较忽略任何前导零后的整数值。比如"0.1"和"0.01"的版本号是相等的
二. 如果版本号没有指定某个下标处的修订号，则该修订号视为0。例如，“1.1"的版本号小于"1.1.1”。因为"1.1"的版本号相当于"1.1.0"，第3位修订号的下标为0，小于1
三. version1 > version2 返回1，如果 version1 < version2 返回-1，不然返回0.
数据范围：
1 <= version1.length, version2.length <= 10001<=version1.length,version2.length<=1000
version1 和 version2 的修订号不会超过int的表达范围，即不超过 32 位整数 的范围
进阶： 时间复杂度 O(n)
示例1
输入：“1.1”,“2.1”
返回值：-1
说明：version1 中下标为 0 的修订号是 “1”，version2 中下标为 0 的修订号是 “2” 。1 < 2，所以 version1 < version2，返回-1
示例2
输入：“1.1”,“1.01”
返回值：0
说明：version2忽略前导0，为"1.1"，和version相同，返回0
示例3
输入：“1.1”,“1.1.1”
返回值：-1
说明：“1.1"的版本号小于"1.1.1”。因为"1.1"的版本号相当于"1.1.0"，第3位修订号的下标为0，小于1，所以version1 < version2，返回-1
示例4
输入：“2.0.1”,“2”
返回值：1
说明：version1的下标2>version2的下标2，返回1
示例5
输入：“0.226”,“0.36”
返回值：1
说明：226>36，version1的下标2>version2的下标2，返回1
思路分析：
这道题最令人头疼的是前置0，那么我们就可以把每个
.
之前的字符串转换为数字，然后比较，就可以消除前置0的影响。
intcompare(char* version1,char* version2 ){int sz1 =strlen(version1), sz2 =strlen(version2);int i =0, j =0;while(i < sz1 || j < sz2){//统计.之前的数字longlong num1 =0, num2 =0;while(i < sz1 && version1[i]!='.'){
num1 = num1 *10+(version1[i]-'0');
i++;}//跳过.
i++;while(j < sz2 && version2[j]!='.'){
num2 = num2 *10+(version2[j]-'0');
j++;}//跳过.
j++;//比较大小if(num1 < num2){return-1;}elseif(num1 > num2){return1;}}return0;}
三、小结
二分查找是在面试中考的非常多的知识点，一定要掌握方法，排序的八种方法也要烂熟于心。
点击链接一起刷题吧
版权归原作者 命由己造～ 所有， 如有侵权，请联系我们删除。