-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathOrderedArray.java
More file actions
152 lines (136 loc) · 3.74 KB
/
OrderedArray.java
File metadata and controls
152 lines (136 loc) · 3.74 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
package sort;
import java.util.Arrays;
public class OrderedArray {
/*
* I have used Integer, rather than int, so that we can do null checks to
* see if data is present at a particular index or not. This is because java
* automatically initializes all elements of arrays, so an int[] will get
* initialized to all 0 values. So it will be hard to see if a 0 was really
* inserted as part of data, or it is the initialized 0.
*/
private Integer[] data;
/**
* We can create an OrderedArray which can hold data upto this size
*
* @param size
*/
public OrderedArray(int size) {
this.data = new Integer[size];
}
public OrderedArray() {
this(100); // default size of the array is 100.
}
/**
* This method implements the binary search algorithm
* in an iterative way
* @param item
* @return the index of the item if found, -1 otherwise
*/
public int binarySearch(int item) {
int maxIndex = size()-1;
int minIndex = 0;
int indexToLook = (int) Math.floor((minIndex + maxIndex) / 2);
while ((data[indexToLook] != item) && (maxIndex > minIndex)) {
if (data[indexToLook] > item) { // case to search on the left
maxIndex = indexToLook - 1;
} else {
minIndex = indexToLook + 1;
}
indexToLook = (int) Math.floor((minIndex + maxIndex) / 2);
}
if (data[indexToLook] == item) return indexToLook;
return -1;
}
/**
* This method implements the binary search algorithm
* in a recursive way. You may take a look at it after completing
* the chapter on recursion.
* @param item
* @return the index of the item if found, -1 otherwise
*/
// public int binarySearch(int item) {
// return binarySearch(item, 0, size()-1);
// }
private int binarySearch(int item, int minIndex, int maxIndex) {
if (minIndex == maxIndex) {
if (data[minIndex] == item)
return minIndex;
return -1;
}
int indexToLook = (int) Math.floor((minIndex + maxIndex) / 2);
if (data[indexToLook] == item) {
return indexToLook;
}
if (data[indexToLook] > item) {
return binarySearch(item, minIndex, indexToLook - 1);
}
// if we are here, then data[indexToLook] < item
return binarySearch(item, indexToLook + 1, maxIndex);
}
public int insert(int item) {
int i = 0;
while ((i < data.length) && (data[i] != null)) {
if (data[i] > item)
break;
i++;
}
/*
* right now i must be pointing to the element which is just greater
* than item so we need to first move all elements from index i onwards
* to right by one
*/
shiftElementsToRight(i);
data[i] = item;
return i;
}
public int delete(int item) {
int i = binarySearch(item);
if (i >= 0) {
shiftElementsToLeft(i + 1);
}
return i;
}
/*
* This method gives the size upto which elements are present. Because
* array length is fixed, all elements will be null initially, then as and
* when we add elements, the elements will become not null. So this tells
* how many elements are really present in this ordered array
*/
private int size() {
int i = 0;
while ((i < data.length) && (data[i] != null)) {
i++;
}
return i;
}
private void shiftElementsToRight(int startIndex) {
for (int i = size()-1; i >= startIndex; i--) {
data[i + 1] = data[i];
}
}
private void shiftElementsToLeft(int startIndex) {
int maxIndex = size()-1;
for (int i = startIndex; i <= maxIndex; i++) {
data[i - 1] = data[i];
}
data[maxIndex] = null;
}
@Override
public String toString() {
return Arrays.deepToString(this.data);
}
public static void main(String[] args) {
OrderedArray oa = new OrderedArray(10);
oa.insert(5);
oa.insert(4);
oa.insert(10);
oa.insert(7);
oa.insert(3);
oa.insert(6);
oa.insert(8);
System.out.println(oa);
System.out.println(oa.binarySearch(8));
oa.delete(5);
System.out.println(oa);
}
}