# LinearSearch

**Repository Path**: cc_zzm/linear-search

## Basic Information

- **Project Name**: LinearSearch
- **Description**: 算法与数据结构（一）：线性查找法
- **Primary Language**: Java
- **License**: Apache-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2020-10-19
- **Last Updated**: 2022-05-31

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

## 算法与数据结构（一）：线性查找法

## 1.什么是算法

一系列解决问题的，清晰，可执行的计算机指令。

## 2.算法的五大特性

1. 有限性
2. 确定性：不会产生二义性
3. 可行性
4. 输入
5. 输出

## 3.线性查找法

**定义：**线性查找又称顺序查找，是一种最简单的查找方法，它的基本思想是从第一个记录开始，逐个比较记录的关键字，直到和给定的K值相等，则查找成功；若比较结果与文件中n个记录的关键字都不等，则查找失败

**举例：**在data数组中查找16

从数组的第一个元素24开始查找，直到找到16，返回其索引4，如果没有找到，则返回-1。

![image-20201017225049886](assets/image-20201017225049886.png)



### 4.实现线性查找法

创建一个`LinearSearch`类，里面定义静态`search()`方法，把空参构造声明为私有的，避免外部使用`new`创建该对象。

```java
public class LinearSearch {

    private LinearSearch() {};
  
		/**
     * 如果查询到目标元素，则返回目标元素所在的索引；查询不到，返回-1
     * @param data 元数据数组
     * @param target 查询目标元素
     * @return
     */
    public static int search(int[] data, int target) {
        for (int i = 0; i < data.length; i++) {
            if (data[i] == target) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {

        int[] data = {24, 18, 12, 9, 16, 66, 32, 4};
				//查找data数组里为16的
        int res = LinearSearch.search(data, 16);
        System.out.println(res);
				//查找data数组里为999的
        int res2 = LinearSearch.search(data, 999);
        System.out.println(res2);
    }
}
```



### 5.使用泛型

用户的数据类型可能是千奇百怪的，有可能是字符型、chat类型、浮点型，也有可能是用户自己设计的一个类，比如说的`Student`类，在`Student`数组中查找某一个相应的`学生`，那么这些需求呢，我们现在的这个线性查找算法`LinearSearch`中的`search()`方法 ，都是无法满足的，接下来我们就要使用`泛型`解决这个问题。

> **使用泛型需要注意的地方：不可以是基本数据类型，只能是类对象**

现在的泛型是类对象，我们要把`if (data[i] == target)`修改成`if (data[i].equals(target))`，因为`==`判断的是引用相等，而`equals`判断的是值相等。

```java
public class LinearSearch {

    private LinearSearch() {};

    /**
     * 如果查询到目标元素，则返回目标元素所在的索引；查询不到，返回-1
     * @param data 元数据数组
     * @param target 查询目标元素
     * @return
     */
    public static <E> int search(E[] data, E target) {
        for (int i = 0; i < data.length; i++) {
            if (data[i].equals(target)) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {

        Integer[] data = {24, 18, 12, 9, 16, 66, 32, 4};

        int res = LinearSearch.search(data, 16);
        System.out.println(res);

        int res2 = LinearSearch.search(data, 999);
        System.out.println(res2);
    }
}
```



### 6.使用自定义类测试我们的算法

定义一个`Student`类，里面有个`name`属性，一个全参构造，然后重写`equals()`方法，实现自己的比较逻辑。

```java
public class Student {

    private String name;

    public Student(String name) {
        this.name = name;
    }


    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }


    @Override
    public boolean equals(Object o) {
        if (this == o)
            return true;

        if (o == null)
            return false;

        if (this.getClass() != o.getClass())
            return false;

        Student student = (Student) o;
        return this.name.equals(student.name);
    }

}
```

在main函数中使用这个类来测试线性查找法。

``` java
public static void main(String[] args) {
  
        Student[] students = {new Student("zzm"), new Student("zhangsan"), new Student("lisi")};
        Student zzm = new Student("zzm");
        int res3 = LinearSearch.search(students, zzm);
        System.out.println(res3);
    }
```



### 7.循环不变量