当前位置：首页 > article >正文

递归、排序、二分查找(C语言实现)

article 2024/9/23 6:34:55

文章目录

递归
排序算法
- 冒泡排序(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;
}