数组的基本操作

这一章记录下java数组的基本操作，如增、删、改、查等。。

准备工作：

新建一个数组类LuLuArray，里面封装了一个数组，在里面实现增删改查的操作。

代码如下：

public class LuluArray {

	//声明一个long类型的数组
	private long[] longArr;
	//表示该数组的有效长度
	private int arrLength;

    /**
	 * 数组类的构造函数
	 */
	public LuluArray(int maxSize) {
		longArr = new long[maxSize];
	}

	
	
}

1、新增操作

1、在数组中无序添加元素

/**
	 * 无序添加数据
	 * @param value
	 */
	public void add(long value) {
		longArr[arrLength] = value;
		arrLength++;
	}

每新添加一个元素，数组长度arrLength加一

2、在数组中有序添加元素

/**
	 * |有序添加数据
	 * @param value
	 */
	public void orderAdd(long value) {
		int i;
		//找缝隙，找到比插入值大的位置
		for(i=0;i<arrLength;i++) {
			if(longArr[i]>value) {
				break;
			}
		}
		//从新值插入的位置开始，后面的值都往后挪一位
		for(int j=arrLength;j>i;j--) {
			longArr[j] = longArr[j-1];
		}
		longArr[i] = value;
		arrLength++;
		
	}

在该数组现有的元素中遍历查找比插入值大的元素，在该元素的前面位置进行插入，插入位置后面的元素的数组下表都进行加一，数组长度加一。如下图所示

2、删除操作

/**
	 * 根据索引删除数据
	 * @param index
	 */
	public void delete(int index) {
		if(index<0 || index>=arrLength) {
			throw new ArrayIndexOutOfBoundsException();
		}else {
			//在index开始往后的数值都往前面挪一位；
		
			for(int i=index; i<arrLength; i++) {
				longArr[i] = longArr[i+1];
			}
			//索引减一
			arrLength--;
		}
	}

在参数index位置往后的元素都往前挪一位，数组长度减一

3、修改操作

/**
	 * 更新数据
	 * @param index
	 * @param newValue
	 */
	public void update(int index,long newValue) {
		if(index<0 || index>=arrLength) {
			throw new ArrayIndexOutOfBoundsException();
		}else {
			longArr[index] = newValue;
		}
	}

根据传入的数组下标和新值进行替换。

4、查找操作

1、根据数组下标查找数据

/**
	 * 根据索引查询数据
	 * @param index
	 * @return
	 */
	public long getData(int index) {
		if(index<0 || index>=arrLength) {
			throw new ArrayIndexOutOfBoundsException();
		}else {
			return longArr[index];
		}
	}

2、根据值查找数组位置

/**
	 * 根据值查找索引
	 * @param value
	 * @return
	 */
	public int search(long value) {
		int i;
		for(i=0;i<arrLength;i++) {
			if(longArr[i] == value) {
				break;
			}	
		}
		//如果i的值等于arrLength说明没有要查找的值
		if(i == arrLength) {
			return -1;
		}else {
			return i;
		}
		
	}

根据参数传入的值对数组进行遍历，查找到返回数组下标，找不到返回-1

3、二分法查找

/**
	 * 二分查找法
	 * @param value
	 * @return
	 */
	public int midlSearch(long value) {
		int middle;
		int begin = 0;
		int end = arrLength;
		
		while(true) {
			middle = (begin+end)/2;
			if(longArr[middle] == value) {
				return middle;
			}else if(begin>end) {
				return -1;
			}else {
				if(longArr[middle] > value) {
					end = middle-1;
				}else {
					begin = middle+1;
				}
			}
		}
		
	}

二分法查找的前提是该数组的元素都是有序的。首先找到该数组的中间值跟参数传入值进行比较。如果参数比中间值大，则在后半块按照上述步骤继续二分法查找，一直找到为止。如果参数比中间值小，则在前半块进行查找。