数据结构java版之《数组》

本篇文章，使用java语言，封装一个数组工具类。不使用系统提供的api。

包括一些数组的增删改查，有序添加，二分查找等功能。

package ch01;public class MyArray {	// 底层内部的数组	PRivate long[] arr;	// 数组容量，记录用户使用数组的长度	private int elements;	/**	 * 无参构造,设置默认数组大小。	 */	public MyArray() {		arr = new long[50];	}	/**	 * 带参构造，用户指定数组大小	 * 	 * @param size	 */	public MyArray(int size) {		arr = new long[size];	}	/**	 * 往数组增加元素（增）	 */	public void insert(int value) {		arr[elements] = value;		// 添加元素，容器记录值也要增加		elements++;	}	/**	 * 在指定位置添加元素	 * 	 * @param index	 * @param value	 */	public void insert(int index, int value) {		// 创建新的数组，比原来数组长度多1		long[] tempArray = new long[elements + 1];		//新插入的位置，就制定添加在索引处		tempArray[index] = value;		// 判断数组角标越界		if (index < 0 || index >= elements) {			throw new ArrayIndexOutOfBoundsException();		} else {			for (int i = 0; i < elements; i++) {				if (i < index) {					//原来数组索引左侧全部给新数组左侧					tempArray[i] = arr[i];				} else {					//原来数组索引位置往后全部赋值给新数组索引后边的位置					tempArray[i + 1] = arr[i];				}			}		}		// 把最新数组赋值给最初的数组		arr = tempArray;		elements++;	}		/**	 * 添加的数据，默认自然排序	 * @param value	 */	public void insertOrder(long value){		int i = 0;		for (i = 0; i < elements; i++) {			//比较,添加的元素第一次小于数组位置元素时，跳出循环，该i值位置就是添加元素的位置			if(value < arr[i]){				break;//跳出循环后，i的值保留，就是要添加数据的数组索引位置			}		}				//倒着遍历		for (int j = elements; j > i; j--) {			//原来数组i位置以后的数组，重新 以次 往后一个位置赋值。这样才可以保证添加元素在最小位置，保证排序			arr[j] = arr[j-1];		}				//把添加元素，加载指定位置		arr[i] = value;		//添加一次，容器标记加一		elements++;	}	/**	 * 遍历数组	 */	public void disPlay() {		System.out.print("[");		for (int i = 0; i < elements; i++) {			if (i == elements - 1) {				System.out.println(arr[i] + "]");			} else {				System.out.print(arr[i] + " ");			}		}	}	/**	 * 根据索引，获取索引位置的值	 * 	 * @param index	 * @return	 */	public long get(int index) {		// 判断数组角标越界		if (index < 0 || index >= elements) {			throw new ArrayIndexOutOfBoundsException();		} else {			return arr[index];		}	}	/**	 * 删除指定索引位置的值	 * 	 * @param index	 */	public void remove(int index) {		// 判断数组角标越界		if (index < 0 || index >= elements) {			throw new ArrayIndexOutOfBoundsException();		} else {			for (int i = index; i < elements; i++) {				// 把index位置的数据替换掉了				arr[i] = arr[i + 1];			}			elements--;		}	}	/**	 * 修改某个位置的数据	 * 	 * @param index	 */	public void upData(int index, int value) {		// 判断数组角标越界		if (index < 0 || index >= elements) {			throw new ArrayIndexOutOfBoundsException();		} else {			arr[index] = value;		}	}	/**	 * 根据值找出对应的索引，找不到就返回-1	 * 线性查找。	 * @param value	 * @return	 */	public int search(int value) {		int index = -1;		for (int i = 0; i < elements; i++) {			if (arr[i] == value) {				index = i;			}		}		return index;	}		/**	 * 二分查找，超找元素的索引。	 * 前提：必须是有序数组。无需数组通过上述线性查找方式	 * @param value	 * @return	 */	public int binarySearch(long value){		/*1、记录最大索引、最小索引		2、计算中间索引		3、比较中间索引值与添加元素		        相等  ：  直接返回		        不相同		            大了  往左查找   max = middle-1;		            小了  往右查找   min = middle+1;		返回2		当min > max 的时候，跳出循环表示查找不到数据。返回-1。*/		int max = elements-1;		int min = 0;		int middle = 0;		while(true){			middle = (max+min)/2;			// 相等  ：  直接返回			if(arr[middle] == value){				return middle;			}else if(arr[middle] > value){				//大了 左边查找				max = middle -1;			}else {				//小了  往右查找				min = middle +1;			}						if(min > max){				return -1;			}		}	}}
微信搜索公众号    codeHoward   在公众号可以最早获取博客最新更新消息，以及了解一些大公司面试经验。