算法知识

月伴飞鱼 2024-11-11 10:00:45
算法相关
支付宝打赏 微信打赏

如果文章对你有帮助,欢迎点击上方按钮打赏作者!

排序算法

排序算法的稳定性

当输入元素中有两个元素的值相同时,排序后完成之后,这两个元素的前后位置是否发生了前后变化。

内排序:

所有排序操作都在内存中完成。

外排序:

由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行。

十大排序算法

冒泡排序

核心思路:

依次比较相邻的两个数,将小数放在前面,大数放在后面。

第一趟:

  • 首先比较第1个和第2个数,将小数放前,大数放后。

  • 然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后。

  • 至此第一趟结束,将最大的数放到了最后。

第二趟:

仍从第一对数开始比较(因为可能由于第2个数和第3个数的交换,使得第1个数不再小于第2个数),将小数放前,大数放后,一直比较到倒数第二个数(倒数第一的位置上已经是最大的)。

第二趟结束,在倒数第二的位置上得到一个新的最大数(其实在整个数列中是第二大的数)。

如此下去,重复以上过程,直至最终完成排序。

举例说明:4 5 6 3 2 1,从小到大排序

第一次冒泡的结果:4 5 6 3 2 1->4 5 3 6 2 1 -> 4 5 3 2 6 1 -> 4 5 3 2 1 6,6这个元素的位置确定了

第二次冒泡的结果:4 5 3 2 1 6->4 3 5 2 1 6 -> 4 3 2 5 1 6 -> 4 3 2 1 5 6,5这个元素的位置确定了

第三次冒泡的结果:4 3 2 1 5 6->3 4 2 1 5 6 -> 3 2 4 1 5 6 -> 3 2 1 4 5 6,4这个元素的位置确定了

第四次冒泡的结果:3 2 1 4 5 6->2 3 1 4 5 6 -> 2 1 3 4 5 6,3这个元素的位置确定了

第五次冒泡的结果:2 1 3 4 5 6->1 2 3 4 5 6,2这个元素的位置确定了

image-20231011155324748

实现:设数组长度为N:

1、比较相邻的前后二个数据,如果前面数据大于后面的数据,就将二个数据交换。

2、这样对数组的第0个数据到N-1个数据进行一次遍历后,最大的一个数据就沉到数组第N-1个位置。

3、循环N=N-1,如果N不为0就重复前面二步,否则排序完成。

public class BubbleSort {
    public static void BubbleSort(int[] arr) {
        int temp;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j + 1] < arr[j]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int arr[] = new int[]{1, 6, 2, 3, 22};
        BubbleSort.BubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

冒泡排序法存在的不足及改进方法

在排序过程中,执行完最后的排序后,虽然数据已全部排序完毕,但程序无法判断是否完成排序。

为了解决这一不足,可设置一个标志位flag,将其初始值设置为非0,表示被排序的表是一个无序的表,每一次排序开始前设置flag值为0,在进行数据交换时,修改flag为非0。

在新一轮排序开始时,检查此标志,若此标志为0,表示上一次没有做过交换数据(有序状态),则结束排序;否则进行排序;

import java.util.Arrays;
public class BubbleSort {
    public static void main(String[] args) {
        int data[] = { 4, 5, 6, 3, 2, 1 };
        int n = data.length;
        for (int i = 0; i < n - 1; i++) {	//排序的次数
            boolean flag = false;
            for (int j = 0; j < n - 1 - i; j++) {	//具体冒泡 n - 1 - i
                if (data[j] > data[j + 1]) {
                    int temp = data[j];	
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                    flag = true;
                }
            }
            if(!flag) break;
        }
        System.out.println(Arrays.toString(data));
    }
}

选择排序

首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾,以此类推,直到所有元素均排序完毕。

由于存在数据交换,选择排序不是稳定的排序算法。

image-20231011155637056
public class SelectionSort {
    public int[] selectionSort(int[] A, int n) {
        //记录最小下标值
        int min=0;
        for(int i=0; i<A.length-1;i++){
            min = i;
            //找到下标i开始后面的最小值
            for(int j=i+1;j<A.length;j++){
                 if(A[min]>A[j]){
                     min = j;
                 }
            }
            if(i!=min){
                swap(A,i,min);
            }
        }
        return A;
    }
    private void swap(int[] A,int i,int j){
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}

插入排序

通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

image-20231011155741461

public class InsertionSort {
    public int[] insertionSort(int[] A, int n) {
      //用模拟插入扑克牌的思想
        //插入的扑克牌
        int i,j,temp;
        //已经插入一张,继续插入
        for(i=1;i<n;i++){
            temp = A[i];
            //把i前面所有大于要插入的牌的牌往后移一位,空出一位给新的牌
            for(j=i;j>0&&A[j-1]>temp;j--){
                A[j] = A[j-1];
            }
            //把空出来的一位填满插入的牌
            A[j] = temp;
        }
        return A;
    }
}

归并排序

归并排序核心是分治思想:

  • 先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。

若将两个有序表合并成一个有序表,称为二路归并。

归并排序是稳定的排序算法。

在这里插入图片描述

public class MergeSort {
    public static void main(String[] args) {
        int data[] = { 9, 5, 6, 8, 0, 3, 7, 1 };
        megerSort(data, 0, data.length - 1);
        System.out.println(Arrays.toString(data));
    }
 
    public static void mergeSort(int data[], int left, int right) { // 数组的两端
        if (left < right) { // 相等了就表示只有一个数了 不用再拆了
            int mid = (left + right) / 2;
            mergeSort(data, left, mid);
            mergeSort(data, mid + 1, right);
            // 分完了 接下来就要进行合并,也就是我们递归里面归的过程
            merge(data, left, mid, right);
        }
    }
 
    public static void merge(int data[], int left, int mid, int right) {
        int temp[] = new int[data.length];		//借助一个临时数组用来保存合并的数据
        
        int point1 = left;		//表示的是左边的第一个数的位置
        int point2 = mid + 1;	//表示的是右边的第一个数的位置
        
        int loc = left;		//表示的是我们当前已经到了哪个位置了
        while(point1 <= mid && point2 <= right){
            if(data[point1] < data[point2]){
                temp[loc] = data[point1];
                point1 ++ ;
                loc ++ ;
            }else{
                temp[loc] = data[point2];
                point2 ++;
                loc ++ ;
            }
        }
    
        while(point1 <= mid){
            temp[loc ++] = data[point1 ++];
        }
        while(point2 <= right){
            temp[loc ++] = data[point2 ++];
        }
        for(int i = left ; i <= right ; i++){
            data[i] = temp[i];
        }
    }
}

希尔排序

基本思想:

将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的下标相差d,对每组中全部元素进行直接插入排序,然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序。

当增量减到1时,进行直接插入排序后,排序完成。

希尔排序法(缩小增量法) 属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序的方法。

假如:数组的长度为10,数组元素为:25、19、6、58、34、10、7、98、160、0。

image-20231011160236871

public static int[] ShellSort(int[] array) {
  int len = array.length;
  int temp, gap = len / 2;
  while (gap > 0) {
    for (int i = gap; i < len; i++) {
      temp = array[i];
      int preIndex = i - gap;
      while (preIndex >= 0 && array[preIndex] > temp) {
        array[preIndex + gap] = array[preIndex];
        preIndex -= gap;
      }
      array[preIndex + gap] = temp;
    }
    gap /= 2;
  }
  return array;
}

快速排序

快速排序的基本思想:

通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

  • 先从数列中取出一个数作为基准数。
  • 分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
  • 再对左右区间重复第二步,直到各区间只有一个数。
public class QuickSort {
    public static void quickSort(int[]arr,int low,int high){
         if (low < high) {     
             int middle = getMiddle(arr, low, high);     
             quickSort(arr, low, middle - 1);//递归左边            
             quickSort(arr, middle + 1, high);//递归右边   
          }  
    }
    public static int getMiddle(int[] list, int low, int high) {     
        int tmp = list[low];    
        while (low < high) {     
            while (low < high && list[high] >= tmp) {//大于关键字的在右边
                high--;     
            }     
            list[low] = list[high];//小于关键字则交换至左边   
            while (low < high && list[low] <= tmp) {//小于关键字的在左边
                low++;     
            }     
            list[high] = list[low];//大于关键字则交换至左边   
        }     
       list[low] = tmp;           
       return low;                   
    } 
}
public class QuickSort {
 
    public static void quickSort(int data[], int left, int right) {
 
        int base = data[left]; // 基准数,取序列的第一个
        int ll = left; // 表示的是从左边找的位置
        int rr = right; // 表示从右边开始找的位置
        while (ll < rr) {
            // 从后面往前找比基准数小的数
            while (ll < rr && data[rr] >= base) {
                rr--;
            }
            if (ll < rr) { // 表示是找到有比之大的
                int temp = data[rr];
                data[rr] = data[ll];
                data[ll] = temp;
                ll++;
            }
            while (ll < rr && data[ll] <= base) {
                ll++;
            }
            if (ll < rr) {
                int temp = data[rr];
                data[rr] = data[ll];
                data[ll] = temp;
                rr--;
            }
        }
        // 肯定是递归 分成了三部分,左右继续快排,注意要加条件不然递归就栈溢出了
        if (left < ll)
            quickSort(data, left, ll - 1);
        if (ll < right)
            quickSort(data, ll + 1, right);
    }
}

优化

基本的快速排序选取第一个或最后一个元素作为基准。但是,这是一直很不好的处理方法。

如果数组已经有序时,此时的分割就是一个非常不好的分割。

因为每次划分只能使待排序序列减一,此时为最坏情况,快速排序沦为冒泡排序,时间复杂度为O(n^2)

三数取中

一般的做法是使用左端、右端和中心位置上的三个元素的中值作为枢纽元

举例:待排序序列为:8 1 4 9 6 3 5 2 7 0

左边为:8,右边为0,中间为6

我们这里取三个数排序后,中间那个数作为枢轴,则枢轴为6

插入排序

当待排序序列的长度分割到一定大小后,使用插入排序。

原因:对于很小和部分有序的数组,快排不如插排好。

当待排序序列的长度分割到一定大小后,继续分割的效率比插入排序要差,此时可以使用插排而不是快排。

重复数组

在一次分割结束后,可以把与Key相等的元素聚在一起,继续下次分割时,不用再对与key相等元素分割。

在一次划分后,把与key相等的元素聚在一起,能减少迭代次数,效率会提高不少。

在处理过程中,会有两个步骤

  • 第一步,在划分过程中,把与key相等元素放入数组的两端

  • 第二步,划分结束后,把与key相等的元素移到枢轴周围

举例:

待排序序列 1 4 6 7 6 6 7 6 8 6

三数取中选取枢轴:下标为4的数6

转换后,待分割序列:6 4 6 7 1 6 7 6 8 6

枢轴key:6

第一步,在划分过程中,把与key相等元素放入数组的两端

  • 结果为:6 4 1 6(枢轴) 7 8 7 6 6 6

  • 此时,与6相等的元素全放入在两端了

第二步,划分结束后,把与key相等的元素移到枢轴周围

  • 结果为:1 4 6 6(枢轴) 6 6 6 7 8 7

  • 此时,与6相等的元素全移到枢轴周围了

之后,在1 4 和 7 8 7两个子序列进行快排

堆排序

堆是一种特殊的树,只要满足这两点,它就是一个堆。

  • 堆是一个完全二叉树。
  • 堆中每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值。

对于每个节点的值都大于等于子树中每个节点值的堆,叫做大顶堆。

对于每个节点的值都小于等于子树中每个节点值的堆,叫做小顶堆。

一般升序用大根堆,降序就用小根堆。

如何实现一个堆

完全二叉树比较适合用数组来存储。

用数组来存储完全二叉树是非常节省存储空间的。

因为不需要存储左右子节点的指针,单纯地通过数组的下标,就可以找到一个节点的左右子节点和父节点。

比如查找数组arr中某个数的父结点和左右孩子结点,比如已知索引为i的数,那么:

父结点索引:(i-1)/2(这里计算机中的除以2,省略掉小数)

左孩子索引:2*i+1

右孩子索引:2*i+2

所以堆的定义性质:

大根堆:arr(i)>arr(2*i+1) && arr(i)>arr(2*i+2)

小根堆:arr(i)<arr(2*i+1) && arr(i)<arr(2*i+2)

堆排序基本步骤

首先将待排序的数组构造成一个大根堆,此时,整个数组的最大值就是堆结构的顶端

将顶端的数与末尾的数交换,此时,末尾的数为最大值,剩余待排序数组个数为n-1

将剩余的n-1个数再构造成大根堆,再将顶端数与n-1位置的数交换,如此反复执行,便能得到有序数组

以下将针对数组arr[1,2,5,4,3,7]进行大顶堆的数据结构转换。

image-20231011161047880

从最后一个非叶子结点开始(第一个非叶子结点 arr.length/2-1=5/2-1=1,也就是索引为2的结点),从右至左,从下至上进行调整。

由于[5,7]中7元素最大,5和7交换。

最后一个非叶子结点索引减1,找到第二个非叶结点(索引1),由于[4,3,2]中4元素最大,2和4交换。

非叶子结点索引减1,找到第三个非叶结点(索引0),由于[4,1,7]中7元素最大,1和7交换。

这时,交换导致了子根[1,5]结构混乱,继续调整,[1,5]中5最大,交换1和5。

此时,我们就将一个无序序列构造成了一个大顶堆。

将堆顶元素与末尾元素进行交换,使末尾元素最大。

然后继续调整堆,再将堆顶元素与末尾元素交换,得到第二大元素。如此反复进行交换、重建、交换。

最后,就实现了堆排序。

import java.util.Arrays;
 
public class HeapSort {
    public static void main(String[] args) {
        int data[] = { 8, 4, 20, 7, 3, 1, 25, 14, 17 };
        heapSort(data);
        System.out.println(Arrays.toString(data));
    }
 
    public static void maxHeap(int data[], int start, int end) { 
 
        int parent = start;
        int son = parent * 2 + 1; // 下标是从0开始的就要加1,从1就不用
        while (son < end) {
            int temp = son;
            // 比较左右节点和父节点的大小
            if (son + 1 < end && data[son] < data[son + 1]) { // 表示右节点比左节点大
                temp = son + 1; // 就要换右节点跟父节点
            }
            // temp表示的是 我们左右节点大的那一个
            if (data[parent] > data[temp])
                return; // 不用交换
            else { // 交换
                int t = data[parent];
                data[parent] = data[temp];
                data[temp] = t;
                parent = temp; // 继续堆化
                son = parent * 2 + 1;
            }
        }
        return;
 
    }
 
    public static void heapSort(int data[]) {
 
        int len = data.length;
        for (int i = len / 2 - 1; i >= 0; i--) { 
            maxHeap(data, i, len);		
        }
        for (int i = len - 1; i > 0; i--) {
            int temp = data[0];
            data[0] = data[i];
            data[i] = temp;
            maxHeap(data, 0, i);
        }
    }
 
}

LRU算法

LRU全称是Least Recently Used,即最近最久未使用的意思。

如果一个数据在最近一段时间没有被使用,将来被使用的机会也比较小。

实现最不经常使用(LRU)缓存的数据结构:应该支持以下操作:get 和 put。

get(key)

  • 如果键存在于缓存中,则获取键的值(总是正数),否则返回 -1。

put(key, value)

  • 如果键不存在,请设置或插入值。
  • 当缓存达到其容量时,它应该在插入新项目之前,使最不经常使用的项目无效。

解决思路

单链表:

对于 put 操作,会出现以下几种情况:

  • 如果要 put(key,value) 已经存在于链表之中(根据key来判断):

    • 那么需要把链表中旧的数据删除,然后把新的数据插入到链表的头部。
  • 如果要 put(key,value) 的数据没有存在于链表之中:

    • 需要判断缓存区是否已满,如果满的话,则把链表尾部的节点删除,之后把新的数据插入到链表头部。
    • 如果没有满的话,直接把数据插入链表头部即可。

对于 get 操作,则会出现以下情况:

  • 如果要 get(key) 的数据存在于链表中:

    • 则把 value 返回,并且把该节点删除,删除之后把它插入到链表的头部(表示最新用到了该节点数据)。
  • 如果要 get(key) 的数据不存在于链表之中:

    • 则直接返回 -1 即可。

时间、空间复杂度分析

对于这种方法,put 和 get 都需要遍历链表查找数据是否存在,所以时间复杂度为 O(n),空间复杂度为 O(1)

哈希表+单链表

可以考虑采用空间换时间的方式来加快 get 的操作。


用一个额外哈希表(例如HashMap)来存放 key-value。

这样,get 操作就可以在 O(1) 的时间内寻找到目标节点。

还需要删除该元素,并且把该元素插入到链表头部。

  • 删除一个元素,需要定位到这个元素的前驱的,定位到这个元素的前驱,需要 O(n) 时间复杂度。

双向链表+哈希表

采用这两种数据结构的组合,get 操作在 O(1) 时间复杂度。

由于 put 操作要删除的节点一般是尾部节点。

所以可以用一个变量 tai 时刻记录尾部节点的位置,这样,put 操作也可以在 O(1) 时间内完成。

// 链表节点的定义
class LRUNode{
    String key;
    Object value;
    LRUNode next;
    LRUNode pre;

    public LRUNode(String key, Object value) {
        this.key = key;
        this.value = value;
    }
}
// LRU
public class LRUCache {
    Map<String, LRUNode> map = new HashMap<>();
    LRUNode head;
    LRUNode tail;
    // 缓存最大容量,我们假设最大容量大于 1,
    // 当然,小于等于1的话需要多加一些判断另行处理
    int capacity;

    public RLUCache(int capacity) {
        this.capacity = capacity;
    }

    public void put(String key, Object value) {
        if (head == null) {
            head = new LRUNode(key, value);
            tail = head;
            map.put(key, head);
        }
        LRUNode node = map.get(key);
        if (node != null) {
            // 更新值
            node.value = value;
            // 把他从链表删除并且插入到头结点
            removeAndInsert(node);
        } else {
            LRUNode tmp = new LRUNode(key, value);
            // 如果会溢出
            if (map.size() >= capacity) {
                // 先把它从哈希表中删除
                map.remove(tail);
                // 删除尾部节点
                tail = tail.pre;
                tail.next = null;
            }
            map.put(key, tmp);
            // 插入
            tmp.next = head;
            head.pre = tmp;
            head = tmp;
        }
    }

    public Object get(String key) {
        LRUNode node = map.get(key);
        if (node != null) {
            // 把这个节点删除并插入到头结点
            removeAndInsert(node);
            return node.value;
        }
        return null;
    }
    private void removeAndInsert(LRUNode node) {
        // 特殊情况先判断,例如该节点是头结点或是尾部节点
        if (node == head) {
            return;
        } else if (node == tail) {
            tail = node.pre;
            tail.next = null;
        } else {
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
        // 插入到头结点
        node.next = head;
        node.pre = null;
        head.pre = node;
        head = node;
    }
}

带有过期时间的LRU实现

每一个节点放一个过期时间,只要到了这个时间就直接删除即可。

  • 添加一个过期时间队列,和一个过期清除的线程。

  • 清除的时候使用while(true)每次判断队列队首是否过期,然后判断是否返回和清除。

二分算法

二分搜索(折半搜索)是一种在有序数组中查找某一特定元素的搜索算法。

  • 时间复杂度是 O(lgn),非常高效。

基本特点

  • 要求待查找的数组或者区间是排好序的。
  • 如果对数组进行动态的删除和插入操作并完成查找,平均复杂度会变为 O(n)

当输入的数组或者区间是排好序的,同时又不会经常变动,而要求从里面找出一个满足条件的元素的时候,二分搜索就是最好的选择。

解题思路

二分搜索解题思路如下:

  • 从已经排好序的数组或区间中取出中间位置的元素,判断该元素是否满足要搜索的条件,如果满足,停止搜索,程序结束。
  • 如果正中间的元素不满足条件,则从它两边的区域进行搜索。
    • 由于数组是排好序的,可以利用排除法,确定接下来应该从这两个区间中的哪一个去搜索
  • 通过判断,如果发现真正要找的元素在左半区间的话,就继续在左半区间里进行二分搜索。
    • 反之,就在右半区间里进行二分搜索。

解题框架

int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

    while(...) {
     //计算 mid 时需要技巧防止溢出,建议写成: mid = left + (right - left) / 2
        int mid = (right + left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

递归解法:

从排好序的数组 {1, 3, 4, 6, 7, 8, 10, 13, 14} 查找数字 7 是否在里面,如果在,返回它的下标,否则返回 -1。

  • 在计算 middle 下标的时候,不能用 (low + hight) / 2,可能会导致溢出。
  • 在取左半边以及右半边的区间时,左半边是 [low, middle - 1],右半边是[middle + 1, high],这是两个闭区间。
    • 因为已经确定了 middle 那个点不是要找的,就没有必要再把它加入到左、右半边了。
  • 对于一个长度为奇数的数组,例如:{1, 2, 3, 4, 5},按照 low + (high - low) / 2 来计算,middle 就是正中间的那个位置,对于一个长度为偶数的数组,例如 {1, 2, 3, 4},middle 就是正中间靠左边的一个位置。

最后的时间复杂度是 O(logn)

递归写法的代码模板如下:

// 二分搜索函数的定义里,除了要指定数组 nums 和目标查找数 target 之外,还要指定查找区间的起点和终点位置,分别用 low 和 high 去表示。
int binarySearch(int[] nums, int target, int low, int high) {
        // 为了避免无限循环,先判断,如果起点位置大于终点位置,表明这是一个非法的区间,已经尝试了所有的搜索区间还是没能找到结果,返回 -1。 

 if (low > high) {
        return -1;
    }
    // 取正中间那个数的下标 middle。
    int middle = low + (high - low) / 2;
    
    // 判断一下正中间的那个数是不是要找的目标数 target,是,就返回下标 middle。    
    if (nums[middle] == target) {
        return middle;
    }
    
    // 如果发现目标数在左边,就递归地从左半边进行二分搜索。
    if (target < nums[middle]) {
        return binarySearch(nums, target, low, middle - 1);
      } else {
        return binarySearch(nums, target, middle + 1, high);
    }//否则从右半边递归地进行二分搜索。
}

非递归解法:

非递归写法的代码模板如下:

int binarySearch(int[] nums, int target, int low, int high) {
    // 在 while 循环里,判断搜索的区间范围是否有效
    while (low <= high) {
        // 计算正中间的数的下标
        int middle = low + (high - low) / 2;
    
     // 判断正中间的那个数是不是要找的目标数 target。如果是,就返回下标 middle
     if (nums[middle] == target) {
         return middle;
     }
    
     // 如果发现目标数在左边,调整搜索区间的终点为 middle - 1;否则,调整搜索区间的起点为 middle + 1
     if (target < nums[middle]) {
         high = middle - 1;
       } else {
         low = middle + 1;
       }
     }

     // 如果超出了搜索区间,表明无法找到目标数,返回 -1  
     return -1;
}
支付宝打赏 微信打赏

如果文章对你有帮助,欢迎点击上方按钮打赏作者!