COMPUTER SCIENCE
CHAPTER-ARRAYS
🔹 Binary Search
1. Algorithm (step-by-step in words)
1. Take a sorted array.
2. Initialize:
o low = 0
o high = n - 1 (last index).
3. Repeat until low <= high:
o Find the middle index: mid = (low + high) / 2.
o If arr[mid] == target, element is found at index mid.
o If arr[mid] < target, element must be in the right half, so set low
= mid + 1.
o If arr[mid] > target, element must be in the left half, so set high
= mid - 1.
4. If the loop ends without finding, the element does not exist.
2. Java Code (in plain text, not copy-paste format)
class BinarySearch {
public static void main(String[] args) {
int arr[] = {2, 5, 8, 12, 16, 23, 38};
int target = 16;
int low = 0;
int high = [Link] - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == target) {
[Link]("Element found at index " + mid);
return;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
[Link]("Element not found");
}
}
3. Array We Will Use
arr = [2, 5, 8, 12, 16, 23, 38]
target = 16
4. Detailed Trace Table
mid =
Ste lo hig arr[mi Comparison with Action Updated
(low+high)/
p w h d] target (16) Taken low / high
2
Search low = 4,
1 0 6 (0+6)/2 = 3 12 12 < 16
right high = 6
Search low = 4,
2 4 6 (4+6)/2 = 5 23 23 > 16
left high = 4
3 4 4 (4+4)/2 = 4 16 16 == 16 ✅ Found (stop here)
5. Final Result
Target element 16 is found at index 4.
🔹 Linear Search
1. Algorithm (step-by-step in words)
1. Start from the first element of the array.
2. Compare each element with the target.
3. If arr[i] == target, element is found at index i.
4. If the loop finishes without finding, the element is not present.
2. Java Code
class LinearSearch {
public static void main(String[] args) {
int arr[] = {2, 5, 8, 12, 16, 23, 38};
int target = 16;
for (int i = 0; i < [Link]; i++) {
if (arr[i] == target) {
[Link]("Element found at index " + i);
return;
}
}
[Link]("Element not found");
}
}
3. Array We Will Use
arr = [2, 5, 8, 12, 16, 23, 38]
target = 16
4. Detailed Trace Table
Step arr[ Comparison with Action
(i) i] target (16) Taken
0 2 2 ≠ 16 Continue
1 5 5 ≠ 16 Continue
2 8 8 ≠ 16 Continue
3 12 12 ≠ 16 Continue
4 16 16 == 16 ✅ Found
- - - Stop search
5. Final Result
Target element 16 is found at index 4.
🔹 Bubble Sort
1. Algorithm (in words)
1. Bubble Sort compares adjacent elements in the array.
2. If the left element > right element, they are swapped.
3. After the 1st pass, the largest element reaches the last position.
4. After the 2nd pass, the second largest is in the second last place, and
so on.
5. This continues until the array is sorted.
2. Java Code
class BubbleSort {
public static void main(String[] args) {
int arr[] = {5, 1, 4, 2, 8};
int n = [Link];
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-1-i; j++) {
if (arr[j] > arr[j+1]) {
// swap arr[j] and arr[j+1]
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
for (int x : arr)
[Link](x + " ");
}
}
3. Example Array
arr = [5, 1, 4, 2, 8]
4. Detailed Trace Table (Pass by Pass)
🔹 Pass 1 (i = 0, j = 0 → 3)
Compare arr[j] & Swap Array
j
arr[j+1] ? State
[1, 5, 4, 2,
05 > 1 Yes
8]
[1, 4, 5, 2,
15 > 4 Yes
8]
[1, 4, 2, 5,
25 > 2 Yes
8]
[1, 4, 2, 5,
35 > 8 No
8]
👉 Largest element 8 is now at the end.
🔹 Pass 2 (i = 1, j = 0 → 2)
Compare arr[j] & Swap Array
j
arr[j+1] ? State
[1, 4, 2, 5,
01 > 4 No
8]
[1, 2, 4, 5,
14 > 2 Yes
8]
[1, 2, 4, 5,
24 > 5 No
8]
👉 Second largest 5 is in place.
🔹 Pass 3 (i = 2, j = 0 → 1)
Compare arr[j] & Swap Array
j
arr[j+1] ? State
[1, 2, 4, 5,
01 > 2 No
8]
[1, 2, 4, 5,
12 > 4 No
8]
👉 Already sorted till 3rd element.
🔹 Pass 4 (i = 3, j = 0)
Compare arr[j] & Swap Array
j
arr[j+1] ? State
[1, 2, 4, 5,
01 > 2 No
8]
👉 No swaps → array is sorted.
5. Final Sorted Array
[1, 2, 4, 5, 8]
🔹 Selection Sort
1. Algorithm
1. Divide the array into two parts: sorted (left) and unsorted (right).
2. In each pass:
o Find the minimum element from the unsorted part.
o Swap it with the first element of the unsorted part.
3. Repeat until the entire array is sorted.
2. Java Code
class SelectionSort {
public static void main(String[] args) {
int arr[] = {64, 25, 12, 22, 11};
int n = [Link];
for (int i = 0; i < n-1; i++) {
int minIndex = i;
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
for (int x : arr)
[Link](x + " ");
}
}
3. Example Array
arr = [64, 25, 12, 22, 11]
4. Detailed Trace Table (Pass by Pass)
🔹 Pass 1 (i = 0 → unsorted = [64, 25, 12, 22, 11])
Start minIndex = 0 (value = 64)
Compare with rest:
o 25 < 64 → minIndex = 1
o 12 < 25 → minIndex = 2
o 22 < 12 → no change
o 11 < 12 → minIndex = 4
Swap arr[0] and arr[4]
👉 Array after Pass 1: [11, 25, 12, 22, 64]
🔹 Pass 2 (i = 1 → unsorted = [25, 12, 22, 64])
Start minIndex = 1 (value = 25)
Compare with rest:
o 12 < 25 → minIndex = 2
o 22 < 12 → no change
o 64 < 12 → no change
Swap arr[1] and arr[2]
👉 Array after Pass 2: [11, 12, 25, 22, 64]
🔹 Pass 3 (i = 2 → unsorted = [25, 22, 64])
Start minIndex = 2 (value = 25)
Compare with rest:
o 22 < 25 → minIndex = 3
o 64 < 22 → no change
Swap arr[2] and arr[3]
👉 Array after Pass 3: [11, 12, 22, 25, 64]
🔹 Pass 4 (i = 3 → unsorted = [25, 64])
Start minIndex = 3 (value = 25)
Compare with rest:
o 64 < 25 → no change
Swap arr[3] with arr[3] (no effect)
👉 Array after Pass 4: [11, 12, 22, 25, 64]
5. Final Sorted Array
[11, 12, 22, 25, 64]
🔹 Insertion in Array
1. Algorithm (Steps in words)
1. Take an array of size n.
2. Choose the position pos where you want to insert the new element.
3. Shift all elements from pos onwards one step to the right.
4. Place the new element at index pos.
5. Increase the size of the array (n = n+1).
2. Java Code (text format)
class InsertInArray {
public static void main(String[] args) {
int arr[] = new int[10];
arr[0] = 10;
arr[1] = 20;
arr[2] = 30;
arr[3] = 40;
int n = 4;
int pos = 2; // position where to insert (0-based index)
int element = 25;
for (int i = n; i > pos; i--) {
arr[i] = arr[i - 1];
}
arr[pos] = element;
n++;
for (int i = 0; i < n; i++)
[Link](arr[i] + " ");
}
}
3. Example
Initial Array = [10, 20, 30, 40]
Insert 25 at position 2 (0-based index)
4. TTE (Trace Table Explanation)
i (loop Array after
Step
index) operation
Initial - [10, 20, 30, 40]
Shift [10, 20, 30, 40,
i=4
1 40]
Shift [10, 20, 30, 30,
i=3
2 40]
[10, 20, 25, 30,
Insert pos=2
40]
5. Final Array
[10, 20, 25, 30, 40]
🔹 Deletion in Array
1. Algorithm (Steps in words)
1. Take an array of size n.
2. Choose the position pos from where the element is to be deleted.
3. Shift all elements from pos+1 to n-1 one step to the left.
4. Decrease the size of the array (n = n-1).
2. Java Code (text format)
class DeleteInArray {
public static void main(String[] args) {
int arr[] = {10, 20, 30, 40, 50};
int n = 5;
int pos = 2; // delete element at index 2 (0-based → 30)
for (int i = pos; i < n - 1; i++) {
arr[i] = arr[i + 1];
}
n--;
for (int i = 0; i < n; i++)
[Link](arr[i] + " ");
}
}
3. Example
Initial Array = [10, 20, 30, 40, 50]
Delete element at position 2 (0-based index → 30)
4. TTE (Trace Table Explanation)
i (loop Array after
Step
index) operation
[10, 20, 30, 40,
Initial -
50]
[10, 20, 40, 40,
Shift 1 i=2
50]
[10, 20, 40, 50,
Shift 2 i=3
50]
Decrease
n=4 [10, 20, 40, 50]
size
5. Final Array
[10, 20, 40, 50]
🔹 Merging Two Arrays
1. Algorithm (Steps in words)
1. Take two arrays A[] and B[] of sizes n1 and n2.
2. Create a new array C[] of size n1 + n2.
3. Copy all elements of A[] into C[].
4. Copy all elements of B[] into C[] after the last element of A[].
5. Print or use the merged array C[].
2. Java Code (in text format)
class MergeArrays {
public static void main(String[] args) {
int A[] = {2, 4, 6};
int B[] = {1, 3, 5};
int n1 = [Link], n2 = [Link];
int C[] = new int[n1 + n2];
// Copy A[]
for (int i = 0; i < n1; i++)
C[i] = A[i];
// Copy B[]
for (int j = 0; j < n2; j++)
C[n1 + j] = B[j];
// Print merged array
for (int x = 0; x < [Link]; x++)
[Link](C[x] + " ");
}
}
3. Example Arrays
A[] = [2, 4, 6]
B[] = [1, 3, 5]
4. TTE (Trace Table Explanation)
Copying A into C
Ste C[] after
ij
p copy
[2, _, _, _, _,
1 0-
_]
[2, 4, _, _, _,
2 1-
_]
[2, 4, 6, _, _,
3 2-
_]
Copying B into C
Ste C[] after
ij
p copy
[2, 4, 6, 1, _,
1 -0
_]
[2, 4, 6, 1,
2 -1
3, _]
[2, 4, 6, 1,
3 -2
3, 5]
5. Final Merged Array
C[] = [2, 4, 6, 1, 3, 5]