01.按顺序查找元素

归并排序

1.基本思想
2.排序过程
3.代码实现
4.如何优化
5.复杂度
6.使用场景

1.基本思想

顺序查找又称为线性查找，是一种最简单的查找方法。适用于线性表的顺序存储结构和链式存储结构。
查找算法中顺序查找算是最简单的了，无论是有序的还是无序的都可以，只需要一个个对比即可，但其实效率很低。

2.排序过程

逐个进行比较
- 从第一个元素m开始逐个与需要查找的元素x进行比较，当比较到元素值相同(即m=x)时返回元素m的下标，如果比较到最后都没有找到，则返回-1。
优缺点
- 缺点：是当n 很大时，平均查找长度较大，效率低；
- 优点：是对表中数据元素的存储没有要求。另外，对于线性链表，只能进行顺序查找。

3.代码实现

代码如下所示

public static int search(int[] a, int key) {
    for (int i = 0, length = a.length; i < length; i++) {
        if (a[i] == key)
            return i;
    }
    return -1;
}

4.如何优化

在算法中，比较和赋值是比较耗时的。在上个章节的顺序查找实现代码中，存在着数组下标和目标值两种比较，那么能不能转变为一种比较呢？答案是可以的，不过要进行数据预处理，将查找值也放到数列中。比如将要查找的元素放在原数列中的第一位或最后一位(如果需要扩容就进行扩容)。此处将要查找的目标元素放在第一位，预处理示例代码如下：
```
int[] array = {12,3,43,5,9};
int target = 43;
int[] newArray = new int[array.length+1];
newArray[0] = target;
for(int i=0;i<array.length;i++){
	newArray[i+1] = array[i];
}
```
也许有人会问，这样预处理一遍数据，需要将数组中所有数组都移动一遍，岂不是更花费时间？从总体上来看，确实是这样的。但是，面临大量的数据要处理时，常常要进行预处理、清洗等操作，这样会令纯粹处理数据（在该例子中就是搜索固定元素）的时间编的更少，更有效。当数据进行预处理后，搜索时就可以不用再比较两次，示例代码如下：
```
public static int sequenceSearchPlus(int[] arr,int key){
	int n=arr.length-1;
	arr[0]=key;
	while(arr[n]!=key){
		n--;
	}
	return n;
}
```

总的代码如下所示

public class Test {

	public static void main(String[] args) {
		int[] array = {12,3,43,5,9};
		int target = 43;
		int result = sequenceSearchPlus(array,target);
		if(result != -1){
			System.out.println("要查找的元素,在数组中的下标是："+result);
		}else{
			System.out.println("要查找的元素不在数组中");
		}
	}

	public static int sequenceSearchPlus(int[] array,int key){
		int[] newArray = new int[array.length+1];
		newArray[0] = key;
		for(int i=0;i<array.length;i++){
			newArray[i+1] = array[i];
		}
		//对新数组
		int n= newArray.length-1;
		newArray[0]=key;
		while(newArray[n]!=key){
			n--;
		}
		return n-1;
	}
}

测试结果为：

要查找的元素,在数组中的下标是：2

5.复杂度

查找成功
- 查找成功时的平均查找长度为： ASL = 每个元素被查找的概率 * 总的元素的个数=1/n*(1+2+3+…+n) = (n+1)/2 ;
当查找不成功时
- 需要n+1次比较，时间复杂度为O(n)，所以，顺序查找的时间复杂度为O(n)。