数组封装应用及有序数组、二分查找源码实现

常规数组应用需要考虑很多边界问题，现将这些问题封装起来，用户在使用时直接调用方法即可，不需要关心边界，算是对数组应用的高级封装

以下是对数组应用的封装

package com.example.demo.array;

import java.util.Arrays;

public class ArrayDemo {

	private String[] arr; // 数组
	private int nElems; // 存储数据数量
	private int maxElems; // 数组最大存储数量

	public HighArray(int max)
	{
		arr = new String[max];
		nElems = 0;
		maxElems = max;
	}

	/**
	 * 查询值所在数组index
	 * @param searchKey
	 * @return
	 */
	public int find(String searchKey) {
		int index = -1;
		for (int i = 0; i < nElems; i++) {
			if(searchKey.equals(arr[i])){
				index = i;
				break;
			}
		}
		return index;
	} 

	/**
	 * 将值插入到数组中，可自动扩容
	 * @param value
	 */
	public void insert(String value)
	{
		//自动扩容
		if(nElems == maxElems){
			maxElems *= 2;
			arr = Arrays.copyOf(arr, maxElems);
		}
		
		arr[nElems++] = value;
	}

	public boolean delete(String value) {
		int index = find(value);
		if(index == -1) {
			return false;
		}
		
		for (int i = index; i < nElems; i++) {
			arr[i] = arr[i+1]; 
		}
		arr[--nElems] = null;
		
		return true;
	}

	public void display(){
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < arr.length; i++) {
			sb.append(arr[i]).append(" ");
		}
		System.out.println(sb.toString());
	}
	
	public static void main(String[] args) {
		HighArray highArray = new HighArray(5);
		highArray.insert("a");
		highArray.insert("b");
		highArray.insert("c");
		highArray.insert("d");
		highArray.insert("e");
		
		highArray.insert("f");
		highArray.display();
		
		int find = highArray.binaryFind("g");
		System.out.println(find);
		
//		highArray.delete("g");
		highArray.display();
	} 
}

有序数组及二分查找，可直接借用ArrayDemo类，修改insert、find方法即可

	/**
	 * 二分查找
	 * @param searchKey
	 * @return
	 */
	public int binaryFind(String searchKey) {
		int index = -1;
		
		int high = nElems-1;
		int low = 0;
		
		while(true){
			//cannot find
			if(low > high){
				break;
			}
			
			int middle = (high+low)/2;
			String middleValue = arr[middle];
			
			if(middleValue.equals(searchKey)){
				index = middle;
				break;
			}else if(middleValue.compareTo(searchKey) > 0){
				high = middle-1;
			}else{
				low = middle+1;
			}
		}
		return index;
	} 

	/**
	 * 有序数组
	 * @param value
	 */
	public void sortedInsert(String value)
	{
		//自动扩容
		if(nElems == maxElems){
			maxElems *= 2;
			arr = Arrays.copyOf(arr, maxElems);
		}
		
		int insertIndex = nElems;
		for (int i = 0; i < nElems; i++) {
			if(value.compareTo(arr[i]) < 0){
				insertIndex = i;
				break;
			}
		}
		
		if(insertIndex != nElems){
			for (int i = nElems; i > insertIndex; i--) {
				arr[i] = arr[i-1];
			}
		}
		
		arr[insertIndex] = value;
	}