Complexities of Array Operations.
Linear Search - O(N)
Binary Search - O(logn)
Insertion on Unordered Array - O(1)
Insertion on Ordered Array - O(N)
Deletion on Unordered Array - O(N)
Deletion on Ordered Array - O(N)
Unordered Array Program:
package com.algorithm.arrays;
class UnOrderedArray {
private long[] a;
private int numberOfElements;
public UnOrderedArray(int maxSize) {
this.a = new long[maxSize];
}
public boolean find(long searchKey){
for(int ele=0;ele<numberOfElements;ele++){
if(a[ele]==searchKey)
return true;
}
return false;
}
public void insert(long value){
a[numberOfElements++] = value;
}
public boolean delete(long value){
int ele=0;
for(ele=0;ele<numberOfElements;ele++){
if(a[ele]==value)
break;
}
if(ele!=numberOfElements){
for(int k=ele;k<numberOfElements;k++){
if(k<numberOfElements-1)
a[k] = a[k+1];
else
a[k]=0;
}
numberOfElements--;
return true;
}
else{
return false;
}
}
public void display(){
for(int i=0;i<numberOfElements;i++){
System.out.println(a[i]);
}
}
}
public class UnOrderedArrayMain {
public static void main(String[] args){
UnOrderedArray arr = new UnOrderedArray(5);
arr.insert(1);arr.insert(2);arr.insert(3);arr.insert(4);arr.insert(5);
arr.display();
if(arr.find(3)){
System.out.println("Search value found");
}
else{
System.out.println("search value does not found");
}
arr.delete(3);
arr.display();
}
}
Ordered Array Program:
package com.algorithm.arrays;
class OrderedArray {
private long[] a;
private int numberOfElements;
public OrderedArray(int maxSize) {
this.a = new long[maxSize];
}
public int size(){
return numberOfElements;
}
public int find(long searchKey){
int lowerBound = 0;
int upperBound = numberOfElements-1;
while(true){
int currentIndex = (lowerBound + upperBound)/2;
if(a[currentIndex] == searchKey){
return currentIndex;
}
else if(lowerBound > upperBound)
return numberOfElements;
else if(a[currentIndex] > searchKey){
upperBound = currentIndex-1;
}
else
lowerBound = currentIndex+1;
}
}
public void insert(long value){
int i;
for(i=0;i<numberOfElements;i){
//Linear Search Find Where new element fits
if(a[i]>value){
break;
}
}
for(int j=numberOfElements;j>i;j--){
a[j] = a[j-1];
}
a[i] = value;
numberOfElements;
}
public boolean delete(long value){
int index = find(value);
if(index == numberOfElements){
return false;
}
else{
for(int k=index;k<numberOfElements;k++){
if(k<numberOfElements-1)
a[k] = a[k+1];
else
a[k]=0;
}
numberOfElements--;
return true;
}
}
public void display(){
for(int i=0;i<numberOfElements;i++){
System.out.println(a[i]);
}
}
}
public class OrderedArrayMain {
public static void main(String[] args){
OrderedArray arr = new OrderedArray(5);
arr.insert(100);arr.insert(26);arr.insert(3);arr.insert(1);arr.insert(5);
arr.display();
if(arr.find(100)!=arr.size()){
System.out.println("Search value found");
}
else{
System.out.println("search value does not found");
}
arr.delete(3);
arr.display();
}
}