Java实现有序数组及二分查找

代码如下

package com.yuxuan66.algorithm.array;

import java.util.Arrays;

/**
 * 有序数组的实现
 *
 * @author Sir丶雨轩
 * @since 2022/1/19
 */
public class OrderArray {

    private long[] array;
    private int size;

    @Override
    public String toString() {
        return "OrderArray{" +
                "array=" + Arrays.toString(array) +
                ", size=" + size +
                '}';
    }

    public OrderArray() {
        // 默认10个元素，每当空间不足时自动扩容2倍
        this.array = new long[10];
        this.size = 0;
    }

    public int size() {
        return this.size;
    }

    /**
     * 数组扩容
     * 如果长度大于数组长度时每次扩容+10个元素的长度
     */
    private void resize() {
        if (size + 1 > array.length) {
            long[] arr = this.array;
            // 创建新的数组
            this.array = new long[array.length + 10];
            // 把原数组数据复制到新数组上
            System.arraycopy(arr, 0, this.array, 0, arr.length);
        }
    }


    /**
     * 插入一个新元素
     *
     * @param item 元素
     */
    public void insert(long item) {
        // 自动扩容
        resize();
        // 记录当前元素要插入的位置
        int index;
        for (index = 0; index < size; index++) {
            // 由于整个数组是有序的，所以如果数字的第某个元素大于要插入的元素，说明当前元素插入位置就在这里
            // 例：{1,3,5} 插入值为2； 循环第二次下标1，就是要插入元素的位置
            if (this.array[index] > item) {
                break;
            }
        }
        // 从索引位置开始把元素往后移动，
        if (size - index >= 0) {
            System.arraycopy(array, index, array, index + 1, size - index);
        }
        this.array[index] = item;
        this.size++;
    }

    /**
     * 删除指定元素,暂不考虑自动缩少数组大小
     *
     * @param item 元素
     */
    public void del(long item) {
        int index = binaryFind(item);
        System.arraycopy(array, index + 1, array, index, size - index);
        this.size--;
    }

    /**
     * 线性查找
     *
     * @param item 元素
     * @return 结果
     */
    public int lineFind(long item) {
        for (int i = 0; i < this.size; i++) {
            if (this.array[i] == item) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 二分查找
     *
     * @param item 元素
     * @return 结果
     */
    public int binaryFind(long item) {

        // 首先设定下界和上界，以限定所查之值可能出现的区域
        // 在开始时，以数组的第一个元素为下界，以最后一个元素为上界
        int min = 0;
        int max = this.size - 1;

        // 循环检查上界和下界的最中间元素
        while (min <= max) {
            // 找出中间的索引 (开头+结束) / 2 = 中间
            int mid = (min + max) / 2;
            long value = this.array[mid];
            // 如果要查找的值小于这个结果，说明数据在这次二分的左边，则调整上界为中间元素索引-1
            // 如果要查找的值大于这个结果，说明数据在这次二分的右边，则调整下界为中间元素索引+1
            // 如果相等就特么找到了
            if (item < value) {
                max = mid - 1;
            } else if (item > value) {
                min = mid + 1;
            } else {
                return mid;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        OrderArray orderArray = new OrderArray();
        orderArray.insert(1L);

        orderArray.insert(5L);
        orderArray.insert(6L);

        orderArray.insert(9L);
        orderArray.insert(10L);
        orderArray.insert(2L);
        orderArray.insert(3L);
        orderArray.insert(4L);
        orderArray.insert(11L);
        orderArray.insert(7L);
        orderArray.insert(8L);
        orderArray.insert(12L);
        orderArray.del(7L);
        System.out.println(orderArray);
        System.out.println(orderArray.lineFind(8L));
        System.out.println(orderArray.binaryFind(8L));
    }
}