# Ordered Array Data Structure Example

The following is the example code for an ordered array data structure. OrderedArrayDataStructure class encapsulate the array and its algorithms. We could have used binary search to find the position where we can insert element into the array. But for simplicity we can use linear search in insert method.

##### Ordered Array data structure and algorithms
package com.sneppets.dsalgo;

public class OrderedArrayDataStructure {

//reference to array arr
private long[] arr;

//number of elements in the array
private int n;

//constructor
public OrderedArrayDataStructure (int arrSize){

//create array
arr = new long[arrSize];

//no elements yet
n = 0;
}

//method to return number of elements in the array currently
public int size(){
return n;
}

//find element using binary search
public int find (long elementKey){

int lBound = 0;

int uBound = n-1;

int cursIn;

while (true){

cursIn = (lBound + uBound)/2;

if(arr[cursIn] == elementKey){

return cursIn; //found the element
}
else if(lBound > uBound){

return n; //can't find it
}
else { //divide range logic

if(arr[cursIn] < elementKey) {

lBound = cursIn + 1; //it's in upper half

}
else {

uBound = cursIn -1; //it's in lower half
}

} //end of divide range logic

} //end of while

} //end of find

//insert element into array - can use binary search to locate the position where new item will be inserted. But for simplicity we can use linear search in insert().
public void insert(long element){

int i;

for (i=0; i<n; i++)
if(arr[i] > element) //linear search
break;

for (int j=n; j>i; j--) //moving bigger ones up
arr[j] = arr[j-1];

arr[i] = element; //insert the element

n++; //increment the size

} //end of insert

public boolean delete(long element){

int i = find(element); //binary search - to locate the item to be deleted

if (i == n){ //can't find it

return false;
}
else { //found the element

for(int j=i; j<n; j++){ //move larger ones down

arr[j] = arr[j+1];
}

n--; //decrement size

return true;
}

} //end of delete function

//display array contents
public void display(){

for(int i=0; i<n; i++){

System.out.println(arr[i]+ " ");

}

}

}
##### OrderedArrayDataStructureTest.java
package com.sneppets.dsalgo;

public class OrderedArrayDataStructureTest {

public static void main (String[] args){

//array size
int arrSize = 10;

//reference to array data structure
OrderedArrayDataStructure arrayDS;

//create the array
arrayDS = new OrderedArrayDataStructure(arrSize);

//insert 5 elements
arrayDS.insert(11);
arrayDS.insert(33);
arrayDS.insert(55);
arrayDS.insert(22);
arrayDS.insert(44);

//display array elements
arrayDS.display();

//search for element 77
int element = 22;

if(arrayDS.find(element) != arrayDS.size()){
System.out.println("Found element "+ element);
}
else{
System.out.println("Could not find element "+ element);
}

//delete 2 elements
arrayDS.delete(33);
arrayDS.delete(55);

//display again
arrayDS.display();
}

}

11
22
33
44
55
Found element 22
11
22
44