2021-常见问题收集整理

2021-常见问题收集整理-篇章1

　　　　一往情深深几许？深山夕照深秋雨。

简介：2021-常见问题收集整理-篇章1，完善自身技能树，有备无患。

一、顺序查找和二分查找法的时间复杂度分别为多少？

二分查找VS顺序查找图

1、顺序查找

顺序查找的平均时间复杂度为O(logn)，n 是待查数列的长度，因为顺序查找是从头到尾查找，而且是查找了整个数组。当然最好的情况是数组的第 1 个元素就是我们要找的元素，这样可以直接找到，最坏的情况是到最后一个元素时才找到或者没有找到要找的元素。

顺序查找代码：

 1   /**
 2      * 顺序查找
 3      */
 4 public class SequentialSearch {
 5     private int[] array;
 6     public SequentialSearch(int[] array) {
 7         this.array = array;
 8     }
 9    
10     /**
11      * 直接顺序查找
12      * @param key
13      * @return
14      */
15     public int search(int key) {
16         for (int i = 0; i < array.length; i++) {
17             if (array[i] == key) {
18                // 找到了的话返回数组下标
19                 return i;
20             }
21         }
22         return -1;
23     }
24 }