21天经典算法之顺序查找

​
​

活动地址：CSDN21天学习挑战赛

专栏前言:

本专栏主要是算法训练，目的很简单。就是为了进厂
最近官方在组织 21 天挑战赛，趁此机会我也更新一下经典算法的文章
如果想一起“狂”或者交流，欢迎来私聊
还不快趁着这个机会来提升自己💪

👉题目链接

👉顺序查找介绍

顺序查找是按照序列原有顺序对数组进行遍历比较查询的基本查找算法。

原理

对于任意一个序列以及一个给定的元素，将给定元素与序列中元素依次比较，从数组的一边开始，如果找出与给定关键字相同的元素，则查找成功；如果将序列中的元素与其都比较完为止，还没有找到，则查找失败。

复杂度分析

时间复杂度：平均复杂度：O(n)；最好的情况是第一个元素就是要找的元素，复杂度O(1)；最坏的情况是将序列查询到底，复杂度为O(n)；
空间复杂度：复杂度为O(1)；顺序查找是对数组序列顺序的比较，没有使用额外的空间。

👉示例：

输入：
2，3，5，9，7，6，1
5
输出：
true
1
2
3
4
5

输入：
2，3，5，9，7，6，1
10
输出：
false
1
2
3
4
5

👉算法实践

💭
顺序查找比较简单，看一下实践操作

顺序查找

题目描述：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，则返回 -1。

class Solution {
    public int searchInsert(int[] nums, int target) {
        for(int i = 0; i < nums.length; ++i){
            if(nums[i] == target){
                return i;
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10

搜索插入位置

如果更加复杂一点，那么就可以看看这一题

搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
1
2
3
4
5
6
7

提示:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为 无重复元素 的 升序 排列数组
-104 <= target <= 104
1
2
3
4

💭 这一个题除了基本的顺序查找之外，另外加入了将没有找到的数字加入到原来的数组中，可以说是提升。

class Solution {
    public int searchInsert(int[] nums, int target) {
        int temp = 0;
        for(int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                temp = i;
                break;
            } else if (nums[nums.length - 1] < target) {
                temp = nums.length;
                break;
            } else if (nums[0] > target) {
                temp = 0;
            } else if(nums[i] > target) {
                temp = i;
                break;
            }
        }
        return temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

这一题其实用二分查找会更加的简单，后续我会介绍。

👉课后习题

所有的题目不会简单的给你一个顺序查找，都是在此基础上进行提升

​