查找算法之线性查找和二分查找

查找算法即在数据中查找自己指定的值，我们这里是返回对应的下标。
1.线性查找（顺序查找）
很简单：
代码实现：

package chazhao;
import java.util.ArrayList;
import java.util.List;

public class LineChazhao {

    public static void main(String[] args) {
        int[] arr = {2, 5, 4, 6, 5, 4, 6, 4, 9, 6, 4};
        List<Integer> integers = lineChazhao(arr, 40);
        System.out.println(integers.toString());
    }


    public static List<Integer> lineChazhao(int[] arr, int num) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == num) {
                list.add(i);
            }
        }
        if (list.size() == 0) {
            list.add(-1);
        }
        return list;
    }
}

结果：

2.二分查找（折半查找，前提是必须有序，排序算法在前面的文章）
代码实现（这里用的是递归）：

package chazhao;
import java.util.ArrayList;
import java.util.List;

public class BinarySerch {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 8, 8, 9};
        List<Integer> i = binarySerach(arr, 0, arr.length - 1, 8);
        System.out.println(i.toString());
    }

    public static List<Integer> binarySerach(int[] arr, int left, int right, int num) {
        if (arr == null) {
            throw new NullPointerException("目标数组为空!");
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];

        List<Integer> list = new ArrayList<>();
        if (left <= right) {
            if (num > midVal) {

                return binarySerach(arr, mid + 1, right, num);
            }
            if (num < midVal) {
                return binarySerach(arr, left, mid - 1, num);
            }
            if (num == midVal) {
                //左
                int temp = mid - 1;
                while (true) {
                    //循环左边所有的元素，只要发现一个不等于当前找的数字就退出
                    if (temp < 0 || arr[temp] != num) {
                        break;
                    }
                    //退出了说明找到了，如果没找到直接break跳出while
                    list.add(temp);
                    temp--;
                }
                //中间的本来就是
                list.add(mid);
                //右边的
                temp = mid + 1;
                while (true) {
                    //循环左边所有的元素，只要发现一个不等于当前找的数字就退出
                    if (temp > arr.length - 1 || arr[temp] != num) {
                        break;
                    }
                    //退出了说明找到了
                    list.add(temp);
                    temp++;
                }

            }

        }
        return list;
    }
}

结果：