递归、排序、二分查找(C语言实现)
文章目录
- 递归
- 排序算法
- 冒泡排序(bubble sort)
- 插入排序(insertion sort)
- 选择排序(selection sort)
- 归并排序(merge sort)
- 快速排序(quick sort)
- 3种线性排序
- 桶排序
- 计数排序
- 基数排序
- 排序算法总结
- 二分查找(Binary Search)
- 二分查找变体问题
- 查找第一个值等于给定值的元素 & 查找最后一个值等于给定值的元素
- 查找第一个值大于或等于给定值的元素
- 查找最后一个值小于或等于给定值的元素
- 参考文献
说明：本文是作者之前在学习<<数据结构与算法之美>>一书时的学习笔记，并用C语言将相关排序算法和二分查找实现。
递归
递归需要满足的3个条件：
- 待求解问题的解可以分解为几个子问题的解。(子问题就是数据规模更小的问题)
- 待求解问题与分解之后的子问题，只有数据规模不同，求解思路完全相同
- 存在递归终止条件
如何编写递归代码：1、写出递推公式；2、找到终止条件。
在实际编写代码时，一般不用递归，而是将递归代码转换成非递归的，因为递归有可能会导致堆栈溢出。而且有可能导致重复计算(比如斐波那契数列，如果用递归代码实现，则有重复计算)。
尾递归：递归调用是最后一个要执行的语句，并且没有其他局部变量参与最后一个语句的执行。
排序算法
可以把排序算法分为原地排序算法(在原数据存储空间上完成排序操作)和非原地排序算法(需要额外的非常量级的数据存储空间才能完成排序)。
原地排序并不与O(1)空间复杂度划等号。一个排序算法是原地排序算法，但它的空间复杂度可能并不是O(1)。但是，反过来说，一个排序算法的空间复杂度为O(1)，则它肯定是原地排序算法。
我们还可以根据算法的稳定性，将排序算法分为稳定排序算法和不稳定排序算法。稳定排序算法是指排序后，相等的元素之间原本的顺序不会改变的排序算法。而不稳定排序算法是指，经过排序之后，相等元素之间原有的先后顺序有可能会被改变。
冒泡排序(bubble sort)
冒泡排序：通过重复遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作重复进行的，直到没有再需要交换的元素为止。
#include <stdio.h>
void bubbleSort(int arr[], int n)
{
int i,j,temp;
int swapped;
//外层循环控制排序的轮数
for (i = 0;i < n-1;i++)
{
swapped = 0;// 每轮开始时，设置交换标志为0
// 内层循环负责进行元素的比较和交换
for (j = 0;j < n-i-1;j++)
{
// 如果当前元素大于下一个元素，则交换它们
if (arr[i] > arr[j+1])
{
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
swapped = 1; // 发生了交换，设置交换标志位1
}
}
// 如果在某次遍历中没有发生交换，则提前结束排序
if (swapped == 0)
{
break;
}
}
}
- 冒泡排序是原地排序算法吗？
- 由于冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，因此，空间复杂度是O(1)，因此，冒泡排序是一个原地排序算法。
- 冒泡排序是稳定排序算法吗？
- 在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序的稳定性，在冒泡的过程中，我们对两个大小相等的相邻的元素不做交换，这样就能保证相同大小的元素，在排序前后原有的先后顺序不会改变，因此，冒泡排序是稳定排序算法。
- 冒泡排序的时间复杂度
- 在最好的情况下，待排序的数据已经是有序的了，那么只需要进行一遍冒泡操作，就可以结束了，因此，最好的时间复杂度为O(n)。
- 在最坏的情况下，要排序的数据刚好是倒序排列的，则需要进行n次冒泡操作，因此，最坏时间复杂度为O(n^2)。
插入排序(insertion sort)
将数组分为已排序和未排序两部分，每次从未排序部分取出一个元素，在已排序部分找到相应的位置并插入。
#include <stdio.h>
void insertionSort(int arr[], int n)
{
int i,key,j;
// 初始时，已排序部分是arr[0],因此未排序部分的索引是从i=1开始的。
for (i = 1; i < n;i++)
{
key = arr[i]; // 选择未排序的第一个元素
j = i - 1;
// 将选中的元素与已排序的元素进行比较，如果已排序的元素大于选中的元素，则将其向后移动
while (j >= 0 && arr[j] > key)
{
arr[j+1] = arr[j];
j--;
}
// 将选中的元素插入到正确的位置
arr[j+1] = key;
}
}
- 插入排序是原地排序算法吗？
- 是原地排序算法。它的空间复杂度是O(1)
- 插入排序是稳定排序算法吗？
- 对于未排序区间的某个元素，如果在已排序区间存在于它值相同的元素，我们选择将它插入到已排序区间值相同元素的后面，这样就可以保持值相同元素原有的前后顺序不变，因此，插入排序是稳定排序算法。
- 插入排序的时间复杂度
- 在最好情况下，如果是已经排序好的，则时间复杂度是O(n)。
- 在最坏情况下，时间复杂度是O(n^2)。
选择排序(selection sort)
选择排序(selection sort)的实现思路类似于插入排序，也将整个数组划分为已排序区间和未排序区间。不同点在于：选择排序每次从未排序区间中找到最小的元素，将其放到已排序区间的末尾。
#include <stdio.h>
void selectionSort(int arr[], int n)
{
int i, j, min_idx, temp;
// 移动未排序数组的边界(初始时，未排序区间是整个数组,已排序区间的大小为0)
for (i = 0; i < n-1; i++)
{
// 找到未排序区间的最小元素的索引
min_idx = i;
for (j = i+1; j< n;j++)
{
if (arr[j] < arr[min_idx])
{
min_idx = j;
}
}
// 交换找到的最小元素与未排序区间的第一个元素
temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
-
选择排序是原地排序算法吗？
- 是原地排序
-
选择排序是稳定排序算法吗？
- 选择排序不是稳定排序算法。
比如，原始数据是5,8,5,2,9 按照上面的实现，经过第一次选择排序的交换后，最小的元素2可能会与第一个5交换位置，因此两个5的相对位置就被打破了。 -
选择排序的时间复杂度
- 最好和最坏情况下，时间复杂度都是O(n^2)。
归并排序(merge sort)
归并排序是一种高效的排序算法，采用分治法的一个典型应用。它将数组分为两半，对每一半递归地进行归并排序，然后将两个排序号的半部分合并在一起。
归并排序的主要步骤：
1、分解：将当前序列平均分成两半，对每一半递归地进行归并排序
2、解决：在分解的子序列中进行排序
3、合并：将两个已排序的子序列合并成一个最终的排序序列
#include <stdio.h>
#include <stdlib.h>
void merge_sort(int arr[], int n)
{
mergeSort(arr, 0, n-1);
}
// l是数组的左边界,r是数组的右边界
void mergeSort(int arr[], int l, int r)
{
// 递归终止条件
if (l >= r)
{
return;
}
// 找到中间点
int m = l+(r-1)/2;
// 递归地排序两半
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
// 合并两个已排序的半部分
merge(arr, l, m, r);
}
// 合并两个子数组的函数
void merge(int arr[], int l, int m, int r)
{
int i,j,k;
int n1= m-l+1; // 左子数组的大小
int n2= r -m; // 右子数组的大小
// 创建临时数组
int L[n1], R[n2];
// 拷贝数据到临时数组
for (i = 0; i< n1; i++)
{
L[i] = arr[l + i];
}
for (j = 0; j < n2; j++)
{
R[j] = arr[m+1+j];
}
// 合并临时数组回到原数组 arr[l...r]
i = 0; // 初始索引第一个子数组
j = 0; // 初始索引第二个子数组
k = l; // 初始索引合并子数组
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
// 如果L[]中还有剩余元素，拷贝剩余元素
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
// 如果R[]中还有剩余元素，拷贝剩余元素
while (j < n2)
{
arr[k] = L[j];
j++;
k++;
}
}
- 归并排序是原地排序算法吗？
- 归并排序不是原地排序算法，它需要O(n)的额外存储空间。
- 归并排序是稳定排序算法吗？
- 通过merge函数可以确定，归并排序是稳定排序算法。
- 选择排序的时间复杂度
- 归并排序在最好、最坏和平均情况下的时间复杂度均为O(n *logn)，其中n是数组的长度。
快速排序(quick sort)
快速排序也利用了分治算法思想。
如果要排序数组中下标从p到r的数据，那么，我们选择p到r之间的任意一个数据作为pivot(分区点，一般选择最后一个或第一个)，然后遍历从p到r的数据，将小于pivot的放到左边，将大于或等于pivot的放到右边，将pivot放到中间。经过这一步骤处理之后，从p到r的数据就被分成了3个部分。假设pivot现在所在位置的下标是q，那么从p到q-1的数据都小于pivot，中间是pivot，从q+1到r的数据都大于或等于pivot。
根据分治的处理思想，分区完成后，我们递归地排序下标从p到q-1的数据和下标q+1到r的数据，直到待排序区间大小缩小为1，这就说明数组中所有的数据都有序了。
伪代码如下：
quick_sort(A, n)
{
quick_sort_c(A, 0, n-1);
}
// 快速排序递归函数，p，r为下标
quick_sort_c(A,p,r)
{
if p >= r then return;
q = partition(A, p, r); // 分区
quick_sort(A, p, q-1);
quick_sort(A, q+1, r);
}
partition(A,p,r)
{
pivot=A[r];
i=p;
for j=p to r do {
if A[j] < pivot
{
swap A[i] with A[j];
i++;
}
}
swap A[i] with A[r];
return i;
}
C语言实现：
#include <stdio.h>
void swap(int *a, int *b)
{
int t = *a;
*a = *b;
*b = t;
}
int partition(int array[], int low, int high)
{
int pivot = array[high]; // pivot
int i = low; // index of smaller element
for (int j = low; j <=high;j++)
{
// if current element is smaller than pivot
if (array[j] < pivot)
{
swap(&array[i], &array[j]);
i++;
}
}
swap(&array[i], &array[high]);
return i;
}
void quickSort(int array[], int low, int high)
{
if (low >= high)
{
return;
}
// pi is partitioning index
int pi = partition(array, low, high);
// separately sort elements before partition and after partition
quickSort(array, low, pi - 1);
quickSort(array, pi + 1, high);
}
-
快速排序是原地排序算法吗？
- 快速排序是原地排序算法。最好空间复杂度O(logn)。最坏空间复杂度O(n)。
-
快速排序是稳定排序算法吗？
-
快速排序是不稳定排序算法
比如对于原始数据是6,8,7,6,3,5,9,4来说， 假如以最后一个元素作为pivot，在经过第一次分区操作之后，两个6的相对先后顺序会发生改变，因此，快排不是稳定排序算法。
-
-
选择排序的时间复杂度
- 最好时间复杂度：O(n *logn)；最坏时间复杂度O(n^2)。
利用快排的分区方法可以用来求在无序数组中求第K大(或者第K小)，且时间复杂度是O(n)。比如对于4,2,5,12,3这样的数据，从小到大的排序为2,3,4,5,12。因此第2小的元素是3。
思路：选择数组A[0, n-1]中的最后一个元素A[n-1]作为pivot，对数组A[0,n-1]进行原地分区，这样数组就分成了3部分：A[0, p-1]、A[p]、A[p+1, n-1]。
如果K = p+1，那么A[p]就是第K小元素；如果K>p+1，就说明第K小元素出现在A[p+1, n-1]中，我们再按照上面的思路递归地在A[p+1,n-1]中查找。如果K<p+1，就在A[0, p-1]里继续查找。
上面的这个算法也叫快速选择(quick select)算法
#include <stdio.h>
void swap(int *a, int *b)
{
int t = *a;
*a = *b;
*b = t;
}
int partition(int array[], int low, int high)
{
int pivot = array[high]; // pivot
int i = low; // index of smaller element
for (int j = low; j <=high;j++)
{
// if current element is smaller than pivot
if (array[j] < pivot)
{
swap(&array[i], &array[j]);
i++;
}
}
swap(&array[i], &array[high]);
return i;
}
int quickSelect(int arr[], int low, int high, int k)
{
if (k > 0 && k <= high - low + 1)
{
int index = partition(arr, low, high);
// 因为下标是从0开始的，所以是k-1
if (index -low == k-1)
{
return arr[index];
}
if (index - low > k-1)
{
return quickSelect(arr, low, index - 1, k);
}
return quickSelect(arr, index + 1,high, k-index + low -1);
}
// 如果K的在数组长度的范围之外，则返回INT_MAX表示没找到
return INT_MAX
}
3种线性排序
桶排序、计数排序、基数排序这三种排序算法的时间复杂度是O(n)，因此也称为线性排序(linear sort)。之所以能做到线性的时间复杂度，主要是因为它们都不是基于比较的排序算法，排序的过程不涉及元素之间的比较操作。
三种线性排序对待排序的数据有严苛的要求。
桶排序
桶排序(bucket sort)的核心处理思想是先定义几个有序的“桶”，将要排序的数据分到这几个“桶”中，对每个“桶”里的数据单独进行排序，再把每个“桶”里的数据按照顺序依次取出，组成的序列就是有序的了。
这里需要注意几点：
- 待排序数据要容易划分为m个“桶”，并且“桶”与“桶”之间有着天然的大小顺序，这样每个“桶”内的数据都排序完后，桶与桶之间的数据不需要再进行排序了。
- 数据在各个“桶”之间的分布要比较均匀。如果数据经过划分之后，有些“桶”里的数据非常多，有些“桶”的数据非常少，很不平均，那么“桶”内数据排序的时间复杂度就不是常量级了。在极端情况下，如果数据都被集中划分到一个桶里，那么桶排序就退化为时间复杂度是O(nlogn)的排序算法了。
计数排序
计数排序(counting sort)是桶排序的一种特殊情况。当要排序的n个数据所处的范围并不大的时候，如最大值是k，我们就可以把数据划分为k个桶，每个桶内的数据都是相等的，省掉了桶内排序的时间。
基数排序
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。
基数排序有两种方法：
1、最高位优先(MSD, Most Significant Digit first)：从最高位开始进行排序。
2、最低位优先(LSD, Least Significant Digit first)：从最低位开始进行排序
排序算法总结
| 排序算法 | 是否原地排序 | 是否稳定排序 | 平均时间复杂度 |
|---|---|---|---|
| 冒泡排序 | 是 | 是 | O(n^2) |
| 插入排序 | 是 | 是 | O(n^2) |
| 选择排序 | 是 | 否 | O(n^2) |
| 快速排序 | 是 | 否 | O(nlogn) |
| 归并排序 | 否 | 是 | O(nlogn) |
| 桶排序 | 否 | 是 | O(n+k)，k为数据范围 |
| 计数排序 | 否 | 是 | O(n) |
| 基数排序 | 否 | 是 | O(dn)，d为数据维度 |
二分查找(Binary Search)
二分查找，也称折半查找，是一种在有序数组中查找某一特定元素的搜索算法。其核心思想是将查找区间不断地折半，通过将待查找的元素与区间中间位置的元素进行比较，缩小查找范围，直到找到目标元素或确定目标元素不存在为止。二分查找的时间复杂度为O(logn)，其中n是数组的长度，这使得它在处理大规模数据时效率远高于线性查找O(n)。
int binarySearch(int* nums, int numsSize, int target){
if (nums == NULL || numsSize == 0)
{
return -1;
}
int low = 0;
int high = numsSize - 1;
int mid;
while (low <= high) { // 结束的条件是 low > high
mid = low + (high - low) / 2;// 防止溢出
if (nums[mid] == target) {
return mid; // 找到目标，返回索引
} else if (nums[mid] < target) {
low = mid + 1; // 在右半部分继续查找
} else {
high = mid - 1; // 在左半部分继续查找
}
}
return -1;// 未找到目标，返回-1
}
这里需要注意几点：
- 为什么while循环的条件中是 <=，而不是 < ?
因为初始化 high = numsSize - 1，即最后一个元素的索引，而不是numsSize。这两者的区别是前者的搜索范围相当于两端都是闭区间[low, high]，而后者相当于是左闭右开区间[low, high)，因为索引numsSize是越界的。 - 为什么 low = mid + 1和high = mid - 1？
因为我们上面的代码搜索区间是两端闭区间[low, high]，所以当发现mid不是我们要找的target时，由于mid已经找过了，所以需要从这个搜索范围中扣除。因此需要去[mid + 1, high]或者[left, mid - 1]中去查找。 - 上面我们mid的取值是 mid = low + (high - low) / 2。为什么不用 mid = (low + high) / 2呢？因为如果low和high比较大的话，两者之和就有可能会溢出。所以将mid的计算方式改成 mid = low + (high - low) / 2。更进一步，我们还可以优化，将这里除以2的操作转化成位运算 mid = low + ((high-low)>>1)。因为相比除法运算，计算机处理位运算要快得多。
二分查找的局限性
- 二分查找依赖的是顺序表结构，即数组。
- 二分查找针对的是有序数据，因此只能用在插入、删除操作不频繁，一次排序多次查找的场景中。
- 数据量太小不适合二分查找，与直接遍历相比效率提升不明显。但是有一个例外，就是数据之间的比较操作非常费时时，比如数组中存储的都是长度超过300的字符串，那还是使用二分查找来尽量减少比较操作吧。
- 数据量太大也不适合二分查找，因为数组需要连续的空间，若数据量太大，往往找不到存储如此规模数据的连续内存空间。
二分查找变体问题
上述的二分查找是非常简单的一种二分查找：在不存在重复元素的有序数组中，查找值等于给定值的元素。还有几种二分查找的变体问题，比如如下四个：
- 查找第一个值等于给定值的元素
- 查找最后一个值等于给定值的元素
- 查找第一个值大于或等于给定值的元素
- 查找最后一个值小于或等于给定值的元素
查找第一个值等于给定值的元素 & 查找最后一个值等于给定值的元素
LeetCode-34-在排序数组中查找元素的第一个和最后一个位置
题目描述:
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
第一种解法
题解，这里找右边界和左边界是类似的，这里只讲一个左边界：
- 如果当前看到的元素恰好等于 target，那么当前元素有可能是target出现的第1个位置，由于我们要找第1个位置，此时我们应该向左边继续查找。当然, 我们此时可以记下这个元素的位置；
- 如果当前看到的元素严格大于target，那么当前元素一定不是要找的 target出现的第1个位置，第1个位置肯定出现在mid的左边，因此就需要在 [left, mid - 1]区间里继续查找；
如果当前看到的元素严格小于target，那么当前元素一定不是要找的 target出现的第1个位置，第1个位置肯定出现在mid的右边，因此就需要在 [mid + 1, right] 区间里继续查找。
总结一句话就是：如果查找左边界值，就压缩待查找的区间右边界；如果查找右边界值，就压缩待查找的区间左边界。
// 查找第一个值等于给定值的元素
int searchLeftRange(int* nums, int numsSize, int target) {
int left = 0;
int right = numsSize - 1;
int mid;
int result = -1;
while (left <= right) {
mid = left + ((right - left) >>1);
if (nums[mid] == target) {
result = mid;
right = mid - 1;
} else if (nums[mid] < target){
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
// 查找最后一个值等于给定值的元素
int searchRightRange(int* nums, int numsSize, int target) {
int left = 0;
int right = numsSize - 1;
int mid;
int result = -1;
while (left <= right) {
mid = left + ((right - left) >>1);
if (nums[mid] == target) {
result = mid;
left = mid + 1;
} else if (nums[mid] < target){
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
第二种解法
上面是一种解法，下面是另一种思路：
// 查找第一个值等于给定值的元素
int searchLeftRange(int* nums, int numsSize, int target) {
int left = 0;
int right = numsSize - 1;
int mid;
while (left <= right)
{
mid = left + ((right - left) >>1);
if (nums[mid] > target)
{
right = mid - 1;
}
else if (nums[mid] < target)
{
left = mid + 1;
}
else
{
if ((mid == 0) || (nums[mid -1] != target))
{
return mid;
}
else
{
right = mid - 1;
}
}
}
return -1;
}
nums[mid]与要找的target的大小关系有3中：大于、小于和等于。对于nums[mid] > target和nums[mid] < target的情况，都很好理解，这里不做解释。
对于nums[mid]==target，因为我们是要查找的是第一个值等于给定值的元素，当nums[mid]等于要查找的值时，我们需要确认一下nums[mid]是不是第一个值等于要查找的元素，怎么确认呢？
如果mid等于0，即这个元素已经是数组的第一个元素了，那么它肯定是我们要查找的第一个值等于给定值的元素；如果mid不等于0，但nums[mid]的前一个元素nums[mid-1]不等于target，那么也说明nums[mid]就是第一个元素。
如果经过检查之后发现，nums[mid]前面的一个元素nums[mid-1]也等于target，就说明此时的nums[mid]不是我们要查找的第一个值，那么我们就更新right=mid-1，因为要查找的元素肯定出现在[left, mid-1]区间。
类似的，查找最后一个值等于给定值的元素的代码如下。
// 查找最后一个值等于给定值的元素
int searchRightRange(int* nums, int numsSize, int target) {
int left = 0;
int right = numsSize - 1;
int mid;
while (left <= right)
{
mid = left + ((right - left) >>1);
if (nums[mid] > target)
{
right = mid - 1;
}
else if (nums[mid] < target)
{
left = mid + 1;
}
else
{
if ((mid == numsSize -1) || (nums[mid +1] != target))
{
return mid;
}
else
{
low = mid + 1;
}
}
}
return -1;
}
查找第一个值大于或等于给定值的元素
题目描述：
给定一个有序的数组，查找第一个大于等于给定值的元素的下标。例如对于数组[3,4,6,7,10].如果查找第一个大于等于5的元素，则是6，所以返回下标2。
其实仔细想想，这个题目就是查找左边界。所以和【查找第一个值等于给定值的元素】那题的解题思路是一样的，只是那题是在等于目标值时，更新结果。但是本题则是在大于等于目标值时更新。具体请见代码：
// 查找第一个大于等于target的值的下标(相当于查找左边界那题)
int searchFirstGETargetIndex(int *nums, int numsSize, int target) {
int left = 0;
int right = numsSize - 1;
int mid;
int result = -1;
while (left <= right) {
mid = left + ((right - left) >>1);
if (nums[mid] >= target) {
result = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return result;
}
思路同上面的第二种解法：
// 查找第一个大于等于target的值的下标(相当于查找左边界那题)
int searchFirstGETargetIndex(int* nums, int numsSize, int target) {
int left = 0;
int right = numsSize - 1;
int mid;
while (left <= right)
{
mid = left + ((right - left) >>1);
if (nums[mid] >= target)
{
// 如果mid是第一个元素或者前面一个元素小于要查找的值target，则nums[mid]就是我们要查找的第一个大于或等于给定值的元素
if ((mid == 0) || (nums[mid -1] < target))
{
return mid;
}
// 如果nums[mid-1]也大于或等于要查找的值target,则说明要查找的元素在[low, mid-1]区间
else
{
right = mid - 1;
}
}
else
{
// 如果nums[mid] < target，那么要查找的值肯定在[mid+1, right]区间
left = mid + 1;
}
}
return -1;
}
查找最后一个值小于或等于给定值的元素
与上题类似，这个题目其实是【查找最后一个值等于给定值的元素】的变形。
// 查找最后一个小于等于target的值的下标(相当于查找右边界那题)
int searchLastLETargetIndex(int *nums, int numsSize, int target) {
int left = 0;
int right = numsSize - 1;
int mid;
int result = -1;
while (left <= right) {
mid = left + ((right - left) >>1);
if (nums[mid] <= target) {
result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
解法二：
// 查找最后一个小于等于target的值的下标(相当于查找右边界那题)
int searchLastLETargetIndex(int* nums, int numsSize, int target) {
int left = 0;
int right = numsSize - 1;
int mid;
while (left <= right)
{
mid = left + ((right - left) >>1);
if (nums[mid] > target)
{
right = mid - 1;
}
else
{
if ((mid == numsSize -1) || (nums[mid +1] > target))
{
return mid;
}
else
{
low = mid + 1;
}
}
}
return -1;
}
参考文献
1、https://book.douban.com/subject/35474931/
2、https://github.com/labuladong/fucking-algorithm
3、https://leetcode-cn.com/tag/binary-search/