数据结构与算法（java)--排序算法及查找

数据结构与算法（java)–链表

数据结构与算法（Java）–栈和递归

数据结构与算法（java)–排序算法及查找

数据结构与算法（java)–哈希表

数据结构与算法（Java）–数结构

数据结构与算法（Java）–图结构

数据结构与算法（Java）–常见算法

leetcode hot100

排序

常见时间复杂度

一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

时间复杂度O(n)

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

在T(n)=4n²-2n+2中，就有f(n)=n²，使得T（n)/f(n)的极限值为4，那么O(f(n))，也就是时间复杂度为O(n²)

• 对于不是只有常数的时间复杂度忽略时间频度的系数、低次项常数
• 对于只有常数的时间复杂度，将常数看为1

常数阶 O(1)

无论代码执行了多少行，只要没有循环等复杂的结构，时间复杂度都是O(1)

int i = 1;
i++;
1
2

上述代码在执行的时候，它消耗的时候并不随着某个变量的增长而增长，那么无论这类代码有多长，即使有几万几十万行，都可以用o1)来表示它的时间复杂度。

对数阶O(log2n)

while(i<n) {
    i = i*2;
}
1
2
3

线性阶O(n)

for(int i = 0; i<=n; i++) {
	i++;
}
1
2
3

这其中，循环体中的代码会执行n次，消耗的时间是随着n的变化而变化，时间复杂度为O(n)

线性对数阶O(nlog2n)

for(int i = 0; i<n; i++) {
    j = 1;
	while(j<n) {
		j = j*2;
	}
}
1
2
3
4
5
6

此处外部为一个循环，循环了n次。内部也是一个循环，但内部f循环的时间复杂度是log2n
将时间复杂度为O(logn)的代码循环N遍的活，那么它的时间复杂度就是n*O(logN)，即O(nlog2n)

平方阶O(n2)

for(int i = 0; i<n; i++) {
	for(int j = 0; j<n; j++) {
		//循环体
	}
}
1
2
3
4
5

如果把o(n)的代码再嵌套循环一遍，它的时间复杂度就是o(n2)，这段代码其实就是嵌套了2层n循环，它的时间复杂度就是O(nn),
即o(n2)如果将其中一层循环的n改成m，那它的时间复杂度就变成了O(mn)

立方阶O(n3)

for(int i = 0; i<n; i++) {
	for(int j = 0; j<n; j++) {
		for(int k = 0; k<n; k++) {
			//循环体
		}
	}
}
1
2
3
4
5
6
7

可以看出平方阶、立方阶的复杂度主要是否循环嵌套了几层来决定的

冒泡排序

比较相邻的两个元素，如果第一个比第二个大就交换，重复比较至最后一个元素，这样最后一个便是最大的；然后继续这样比较（除了每一轮比较出来的最后一个；即数组长度len-i-1（第几轮）

代码实现

public class Demo1 {
   public static void main(String[] args) {
      int[] arr = {4, 5, 1, 6, 2};
      for(int i = 1; i<arr.length; i++) {
         //定义一个标识，来记录这趟大循环是否发生了交换
         boolean flag = true;
         //只需要比较前length-i个数
         //每次排序会确定一个最大的元素
         for(int j = 0; j<arr.length-i; j++) {
            if(arr[j] > arr[j+1]) {
               int temp = arr[j];
               arr[j] = arr[j+1];
               arr[j+1] = temp;
               //发生了交换，标识改为false
               flag = false;
            }
         }
         //如果这次循环没发生交换，直接停止循环
         if(flag) {
            break;
         }
      }
      for(int i : arr) {
         System.out.println(i);
      }
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

选择排序

1. 从第一个元素开始比较，找到最小（大）的之后放入有序区（刚开始全是无序区），然后从无序区的第一个在开始上述比较，得到最小的，放入有序区

2. 一共需要遍历元素个数-1次，当找到第二大（小）的元素时，可以停止。这时最后一个元素必是最大（小）元素。
   代码实现

public class Demo2 {
	public static void main(String[] args) {
		int[] arr = {3, 1, 6, 10, 2};

		//从第0个元素开始比较，一共循环length-1次，最后一个无须进行排序
		for(int i = 0; i<arr.length-1; i++) {
			//保存最小元素的下标
			int min = i;
			//将该元素与剩下的元素比较，找出最小元素的下标
			for(int j = i+1; j<arr.length; j++) {
				//保存最小元素的下标
				if(arr[j] < arr[min]) {
					min = j;
				}
			}
			//交换元素
			//如果不是arr[i]不是最小的元素，就交换
			if(min != i) {
				int temp;
				temp = arr[i];
				arr[i] = arr[min];
				arr[min] = temp;
			}
		}

		for(int i : arr) {
			System.out.println(i);
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

插入排序

将待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
取出下一个元素，在已经排序的元素序列从后向前扫描；如果该（已排序）元素大于新元素（即取出来的元素），则向后移一位，继续重复比较，直到找到已排序的元素小于等于新元素（稳定排序，不改变原有顺序），将新元素插入该位置；重复上述步骤

public class Demo3 {
   public static void main(String[] args) {
      int[] arr = {3, 1, 6, 10, 2};
      //从数组的第二个元素开始选择位置插入
      //因为第一个元素已经放入了有序数组中
      for(int i = 1; i<arr.length; i++) {
         //保存该位置上元素的值,后面移动元素可能会覆盖该位置上元素的值
         int temp = arr[i];
         //变量j用于遍历前面的有序数组
         int j = i;
         while (j>0 && temp<arr[j-1]) {
            //如果有序数组中的元素大于temp，则后移一个位置
            arr[j] = arr[j-1];
            j--;
         }

         //j选择所指位置就是待插入的位置
         if(j != i) {
            arr[j] = temp;
         }
      }
      for(int i : arr) {
         System.out.println(i);
      }
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

希尔排序

思想：希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止

步骤1：选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
步骤2：按增量序列个数k，对序列进行k 趟排序；
步骤3：每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

public class Demo4 {
   public static void main(String[] args) {
      int[] arr = {3, 6, 1, 4, 5, 8, 2, 0};
      int temp;
      //将数组分为gap组,每个组内部进行插入排序
      for(int gap = arr.length/2; gap>0; gap /= 2) {
         //i用来指向未排序数组的首个元素
         for(int i = gap; i<arr.length; i++) {
            temp = arr[i];
            int j = i;
            //找到temp应该插入的位置,需要先判断数组是否越界
            while (j-gap>=0 && temp<arr[j-gap]) {
               arr[j] = arr[j-gap];
               j -= gap;
            }

            if(j != i) {
               arr[j] = temp;
            }
         }
      }

      for(int i : arr) {
         System.out.println(i);
      }
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

快速排序

冒泡排序的改进。
分区：先在序列中以第一个数作为基准数，将基准数移动到序列的中间某个位置，数的左边的都小于它，右边的都大于它（相同的数可以到任一边）（用到了双指针）
然后利用递归（类似归并排序的感觉）在对基准数左边和右边的序列进行第一个步骤，直到所有的数都归位（即第一个步骤的完成条件）

public class Demo5 {
   public static void main(String[] args) {
      int[] arr = {8, 12, 19, -1, 45, 0, 14, 4, 11};
      QuickSort sort = new QuickSort();
      sort.quickSort(arr);
      for(int i : arr) {
         System.out.println(i);
      }
   }
}

class QuickSort {

   /**
    * 快速排序
    * @param arr 待排序的数组
    */
   public void quickSort(int[] arr) {
      if(arr == null || arr.length<=1) {
         return;
      }

      quickSort(arr, 0, arr.length-1);
   }

   /**
    *
    * @param arr 待排序的数组
    * @param left 左侧开始下标
    * @param right 右侧开始下标
    */
   private void quickSort(int[] arr, int left, int right) {
      //如果分区元素小于等于一个，就返回
      if(right <= left) {
         return;
      }

      //得到基数下标
      int partition = partition(arr, left, right);

      //递归左右两个分区,因为每次是以左边的第一个数为基数，所以右边分区递归需要在partition的右侧开始
      quickSort(arr, left, partition);
      quickSort(arr, partition+1, right);
   }


   /**
    * 返回基准下标
    * @param arr 待排序的数组
    * @param left 左侧开始下标
    * @param right 右侧开始下标
    * @return 中间值的下标
    */
    private int partition(int[] arr, int left, int right) {
      //以该分区最左边的数为基数
      int pivot = arr[left];

      while(left < right) {
         //右边下标开始向左移动，找到小于基数的值时停止
         while(right>left && arr[right] >= pivot) {
            right--;
         }
         //交换数值，此时pivot保存了arr[left]的值，所以不会丢失
         arr[left] = arr[right];

         //左边下标开始移动，找到大于基数的值时停止
         while(left<right && arr[left] <= pivot) {
            left++;
         }
         //交换数值
         arr[right] = arr[left];
         //基数插入到合适的位置
         arr[left] = pivot;
      }

      //返回基数下标
      return left;
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

归并排序

把长度为n的输入序列分成两个长度为n/2的子序列；递归拆开至只有一个元素，然后从最短序列开始一次排序、合并；最终合并成为一个有序序列
分而治之—治

public class Demo6 {
   public static void main(String[] args) {
      int[] arr = {1, 5, 6, 3, 2, 8, 7, 4};
      MergeSort mergeSort = new MergeSort(arr.length);
      mergeSort.mergeSort(arr, 0, arr.length-1);
      for(int a : arr) {
         System.out.println(a);
      }
   }
}

class MergeSort {
   /**
    * 临时数组，用于合并时用于存放元素
    */
   int[] temp;


   public MergeSort() {
   }

   public MergeSort(int length) {
      temp = new int[length];
   }

   /**
    * 将分解的序列进行合并，合并的同时完成排序
    * @param arr 待合并的数组
    * @param left 数组左边界
    * @param right 数组右边界
    */
   private void merge(int[] arr, int left, int right) {
      //两个序列的分界点
      int mid = (left+right)/2;
      //temp数组中插入的位置
      int tempLeft = 0;
      int arrLeft = left;
      //第二个序列的首元素下标
      int arrRight = mid+1;

      while(arrLeft<=mid && arrRight<=right) {
         //如果第一个序列的元素小于第二序列的元素，就将其放入temp中
         if(arr[arrLeft] <= arr[arrRight]) {
            temp[tempLeft] = arr[arrLeft];
            arrLeft++;
         }else {
            temp[tempLeft] = arr[arrRight];
            arrRight++;
         }
         tempLeft++;
      }


      //将不为空的序列中的元素依次放入temp中
      while (arrLeft <= mid) {
         temp[tempLeft] = arr[arrLeft];
         tempLeft++;
         arrLeft++;
      }

      while (arrRight <= right) {
         temp[tempLeft] = arr[arrRight];
         tempLeft++;
         arrRight++;
      }

      //将临时数组中的元素放回数组arr中
      tempLeft = 0;
      arrLeft = left;
      while (arrLeft <= right) {
         arr[arrLeft] = temp[tempLeft];
         arrLeft++;
         tempLeft++;
      }
   }

   public void mergeSort(int[] arr, int left, int right) {
      int mid = (left+right)/2;
      if(left < right) {
         mergeSort(arr, left, mid);
         mergeSort(arr, mid+1, right);
         merge(arr, left, right);
      }
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

基数排序(桶排序)

将所有元素变成和最多位数一样的位数，不够的补零，然后按照从个位比较，排好序之后再按高一位的比较，一直到最高位，然后便得到一个有序数列。

疑问： 为什么是从低位开始比较，而不是高位；从高位开始为什么最后得到的不是有序数列？
高位的权重低于低位，高位确定之后，低位在已经确定高位的数据中进行排序就会打乱顺序，所以应该先按低位排序

public class RadixSrort {
    public static void main(String[] args) {
        /*int[] arr = {53,3,542,748,14,214};
        radixsort(arr);*/
        int[] arr = new int[800000];
        int[] temp = new int[arr.length];
        for (int i = 0; i < 800000;i++){
            arr[i] = (int)(Math.random() * 800000);
        }
        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSSS");
        String s1 = simpleDateFormat.format(date1);
        System.out.println("排序前：" + s1);
        radixsort(arr);
        Date date2 = new Date();
        String s2 = simpleDateFormat.format(date2);
        System.out.println("排序后：" + s2);
    }
    public static void radixsort(int[] arr){
        //第一轮排序（针对个位进行处理）
        //定义一个二维数组代表10个桶，每一个桶就是一个一维数组
        int[][] bucket = new int[10][arr.length];
        //为了记录每一个桶中实际存放了多少个数据，我们定义一个一维数组来记录各个桶每次放入的数据个数
        int[] bucketElementCounts = new int[10];//记录每个桶中数据的数量
        int max = arr[0];
        for(int i = 0; i<arr.length;i++){
            if (arr[i]>max){
                max = arr[i];
            }
        }
        //System.out.println("Max为" + max);
        int maxLength = (max + "").length();//转换为字符串
        int n =1;
        for (int i = 0;i<maxLength;i++) {
            for (int j = 0; j < arr.length; j++) {
                //取出每个元素的个/十/百位
                int digitOfElement = arr[j] / n % 10;
                //放入到对应的桶中
                //数组中的第一个数代表这0.1.2...
                //数组中第二个数代表每一个桶中有多少个数
                //bucketElementCounts[digitOfElement] 代表着每一个桶中，元素的索引
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;
            }
            //放入原数组
            int index = 0;
            //遍历每一个桶，并将桶中的数据放入到原数组
            for (int k = 0; k < bucket.length; k++) {
                //如果桶中有数据，我们才放入到原数组
                if (bucketElementCounts[k] != 0) {
                    //说明桶中有数据
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        //取出元素放入到arr
                        arr[index] = bucket[k][l];
                        index++;
                    }
                }
                bucketElementCounts[k] =0;//处理完一个桶之后需要将桶置为0
            }
            n *= 10;
            //System.out.println(Arrays.toString(arr));
        }

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

也可以通过将最大数变为String类型，再求得它的长度

堆排序

堆是具有以下性质的完全二叉树：

• 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆
  注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系
• 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆

一般升序排序采用大顶堆，降序排列使用小顶堆

排序思路

对比

---

排序算法时间复杂度

---

相关术语解释：

1. 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
2. 不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
3. 内排序：所有排序操作都在内存中完成；
4. 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
5. 时间复杂度： 一个算法执行所耗费的时间。
6. 空间复杂度：运行完一个程序所需内存的大小
7. n: 数据规模
8. k: “桶”的个数
9. In-place: 不占用额外内存
10. Out-place: 占用额外内存

---

查找

线性查找

有一个数列： {1,8, 10, 89, 1000, 1234} ，判断数列中是否包含此名称【顺序查找】
要求: 如果找到了，就提示找到，并给出下标值。

查找思路：从数组的一个元素出发，一个个地和要查找的值进行比较，如果发现有相同的元素就返回该元素的下标。反之返回-1（未找到）

package com.atguigu.search;


public class SeqSearch {
    public static void main(String[] args) {
        int arr[] = {1,9,11,-1,34,89};
        System.out.println(seqsearch(arr, 9) == -1? "没有查找到":"找到了，为" + seqsearch(arr,9));

    }
    public static int seqsearch(int[] arr,int values){
        //线性查找是逐一比对，发现有相同值，就返回下标
        //这里我们查找到一个就返回
        for (int i =0; i<arr.length;i++){
            if (arr[i] == values){
                return i;
            }
        }
        return -1;
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

二分查找

进行二分查找的数组必须为有序数组

• 设置一个指向中间元素下标的变量mid，mid=(left + right)/2
• 让要查找的元素和数组mid下标的元素进行比较
  • 如果查找的元素大于arr[mid]，则left变为mid后面一个元素的下标
  • 如果查找的元素小于arr[mid]，则right变为mid前一个元素的下标
  • 如果查找的元素等于arr[mid]，则mid就是要查找元素所在的位置
• 什么时候结束递归
  • 找到就结束递归
  • 递归完整个数组，仍然没有找到findVal ，也需要结束递归 当 left > right 就需要退出（说明元素不在该数组中）

public class Demo2 {
   public static void main(String[] args) {
      //进行二分查找的数组必须是有序
      int[] arr = {0，8，9，17，22};
      int result = binarySearch(arr, 11);
      if(result == -1) {
         System.out.println("未找到该元素");
      }else {
         System.out.println("该元素的下标是：" + result);
      }
   }

   /**
    * 二分查找
    * @param arr 要查找的有序数组
    * @param num 要查找的数字
    * @return 对应数字的下标
    */
   public static int binarySearch(int[] arr, int num) {
      int left = 0;
      int right = arr.length-1;
      while(left <= right) {
         //防止溢出
         int mid = (right - left)/2 + left;
         //如果要查找的值大于中间位置的值，说明要查找的值在右边部分
         if(arr[mid] < num) {
            left = mid + 1;
         }else if(arr[mid] > num) {
            //如果要查找的值小于中间位置的值
            //说明要查找的值在左边部分
            right = mid - 1;
         }else {
            //找到了该元素
            return mid;
         }
      }
      return -1;
   }
}Copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

{1, 10, 22, 22, 100，123} 当一个有序数组中，有多个相同的数值时，如何将所有的数值 都查找到，比如这里的 22 。这时就需要在找到一个元素后，不要立即返回，而是扫描其左边和右边的元素，将所有相同元素的下标保存到一个数组中，然后一起返回

public class Demo2 {
   public static void main(String[] args) {
      int[] arr = {0，6 11, 11, 11, 11, 30};
      //进行二分查找的数组必须是有序
      Arrays.sort(arr);
      List<Integer> result = binarySearch(arr, 11);
      if(result.size() == 0) {
         System.out.println("未找到该元素");
      }else {
         for(Integer index : result) {
            System.out.println(index);
         }
      }
   }

   /**
    * 二分查找（可以查找重复元素的下标）
    * @param arr 要查找的有序数组
    * @param num 要查找的数字
    * @return 保存了所有该值元素所在的位置
    */
   public static List<Integer> binarySearch(int[] arr, int num) {
      int left = 0;
      int right = arr.length-1;
      int mid;
      //用户保存查找值下标
      List<Integer> positionList = new ArrayList<>();
      while(left <= right) {
         mid = (left + right)/2;
         //如果要查找的值大于中间位置的值，说明要查找的值在右边部分
         if(arr[mid] < num) {
            left = mid + 1;
         }else if(arr[mid] > num) {
            //如果要查找的值小于中间位置的值
            //说明要查找的值在左边部分
            right = mid - 1;
         }else {
            //将下标存入到集合中
            positionList.add(mid);
            //用于遍历mid左边的相同元素
            int leftIndex = mid - 1;
            while(leftIndex > 0 && arr[leftIndex] == num) {
               positionList.add(leftIndex);
               leftIndex--;
            }

            int rightIndex = mid + 1;
            while(rightIndex < right && arr[rightIndex] == num) {
               positionList.add(rightIndex);
               rightIndex++;
            }

            return positionList;
         }
      }

      return positionList;
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

插值查找

在二分查找中，如果我们要找的元素位于数组的最前端或者最后段，这时的查找效率是很低的。所以在二分查找基础上，引入了插值查找，也是一种基于有序数组的查找方式
插值查找与二分查找的区别是：插值查找每次从自适应 mid 处开始查找。

mid的值在两种查找算法中的求法：

• 二分查找：mid = (left + right)/2

• 插值查找：

  mid = left + (right - left) * (num - arr[left]) / (arr[right] - arr[left])

  • 其中num为要查找的那个值

public class Demo3 {
   public static void main(String[] args) {
      int[] arr = {-1, -1, 0, 11, 11, 11, 11, 30};
      //进行二分查找的数组必须是有序
      Arrays.sort(arr);
      List<Integer> result = insertSearch(arr, 30);
      if(result.size() == 0) {
         System.out.println("未找到该元素");
      }else {
         for(Integer index : result) {
            System.out.println(index);
         }
      }
   }

   /**
    * 插值查找查找（可以查找重复元素的下标）
    * @param arr 要查找的有序数组
    * @param num 要查找的数字
    * @return 保存了所有该值元素所在的位置
    */
   public static List<Integer> insertSearch(int[] arr, int num) {
      List<Integer> positionList = new ArrayList<>();
      int left = 0;
      int right = arr.length - 1;
      int mid;
      while(left<=right) {
         //插值查找的自适应算法
         mid = left+(right-left)*(num-arr[left])/(arr[right]-arr[left]);
         if(arr[mid] > num) {
            right = mid - 1;
         }else if(arr[mid] < num) {
            left = mid + 1;
         }else {
            //找到了该元素的位置
            positionList.add(mid);
         }

         //继续查找mid附近值相同的元素
         int leftIndex = mid - 1;
         while(leftIndex >=0 && arr[leftIndex] == num) {
            positionList.add(leftIndex);
            leftIndex++;
         }
         int rightIndex = mid + 1;
         while (rightIndex <= right && arr[rightIndex] == num) {
            positionList.add(rightIndex);
            rightIndex++;
         }
         return positionList;
      }
      return positionList;
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

斐波那契查找