Module 2
SEARCHING
BINARY SEARCH
Binary search is another searching technique that takes less time complexity
compared with the linear search technique. Binary search can be applied only on the array
elements which is available in sorted order.
Consider K is an array consists of n elements in sorted order such that K[1] ≤ K[2] ≤ .
. . . ≤ K[n]. Suppose an item of information is given to search in the variable Key. Then
binary search procedure works as:
In binary search technique, first compute
Mid
Where, Low refers to the first index and High refers to last index of the array at the
initial call. Now, the process falls into any one of the following three cases.
Case 1: If Key = K[Mid]; Then the search is successful search i.e., Element Found.
Case 2: If Key > K[Mid]; Then the Key element can appear only in the right half of
the array. So, we reset the Low value as Low = Mid+1 and begin search
again.
Case 3: If Key < K[Mid]; Then the Key element can appear only in the left half of the
array. So, we reset the High value as High = Mid-1 and begin search again.
The above procedure is repeated up to we reach Low > High. When we obtain this
condition, it indicates that the search is unsuccessful search i.e., Element not found.
For this, functional procedure can be placed as:
Non-Recursive Binary Search:
int search(int K[50], int Low, int High, int Key)
{
int Mid;
while(Low <= High)
{
Mid = (Low + High) / 2;
if (Key = = K[Mid])
return Mid;
else if (Key > K[Mid])
Low = Mid + 1;
else
High = Mid – 1;
}
return -1;
}
Algorithm recursiveBinarySearch(k, low, high, key)
Step 1: if low > high then
return -1
endif
Step 2: mid ← (low + high) / 2
Step 3: if key == k[mid] then
return mid
elseif key < k[mid] then
return recursiveBinarySearch(k, low, mid - 1, key)
else
return recursiveBinarySearch(k, mid + 1, high, key)
endif
Program:
public class BinarySearchRecursive
{
public static int binarySearch(int[] arr, int low, int high, int target)
{
// Base case: If the search range is invalid or empty, the element is not
found.
if (low > high)
{
return -1;
}
int mid = low + (high - low) / 2;
// Conquer: Compare the middle element with the target.
if (arr[mid] == target) {
return mid; // Target found at mid index.
} else if (arr[mid] < target) {
// Divide: If target is greater, search in the right half.
return binarySearch(arr, mid + 1, high, target);
} else {
// Divide: If target is smaller, search in the left half.
return binarySearch(arr, low, mid - 1, target);
}
}
public static void main(String[] args)
{
int[] sortedArray = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int target = 23;
// Search for target
int index = binarySearch(sortedArray, 0, [Link] - 1, target);
if (index != -1) {
[Link]("Element " + target + " found at index " + index);
} else {
[Link]("Element " + target + " not found in the array.");
}
}
}
Example: Search an element 44 from the list of elements
11 22 30 33 41 44 55
Solution: Given K[1:7] = 11 22 30 33 41 44 55
Search Element Key = 44
Pass 1: Low = 1 High = 7 1<7 TRUE
Mid = (1+7) / 2 = 4
Key = K[Mid] 44 = 33 FALSE
Key > K[Mid] 44 > 33 TRUE
Hence, Reset Low = 4+1 = 5
Pass 2: Low = 5 High = 7 5<7 TRUE
Mid = (5+7)/2 = 6
Key = K[Mid] 44 = 44 TRUE
SUCCESSFUL SEARCH i.e., ELEMENT FOUND
Analysis of Binary search
The complexity is measured by the number of comparisons to locate the search item
in the given array elements.
In binary search, each comparison reduces the size of the array into half. So that
number of comparisons is less compare to linear search. Hence, the worst case and average
case time complexity of binary search is O (log n).
SORTING
Sorting refers to the arrangement of data items either in the ascending (increasing)
order or in the descending (decreasing) order. Some of the most important sorting
techniques are:
a) Quick Sort
b) Merge Sort
a) QUICK SORT (PARTITION EXCHANGE SORT)
Quick sort is a sorting technique based on the divide-and-conquer strategy. In this
sorting technique, array elements are divided into two sub arrays depending on a specialized
element called “pivot” element.
Let K is an array that consists of ‘n’ elements from index 1 to index n. Sorting refers
to the process of rearranging the given elements of K in ascending order such that: K[1] ≤
K[2] ≤ . . . . . . . . ≤ K[n]. For this quick sort procedure works as:
Step 1: Initialize the first element as pivot element.
Step 2: Initialize a variable i at the first index and another variable j at last index+1.
Step 3: Increment i value by 1 until K[i] ≥ pivot element.
Step 4: Decrement j value by 1 until K[j] ≤ pivot element.
If i < j Then
Interchange K[i] & K[j]
EndIf
Step 5: Repeat Step 3 and 4 until i ≥ j
Step 6: Interchange the values of K[j] and pivot element.
The above process refers to one pass. At the end of the pass, the pivot element is
positioned at its sorted position. At this stage, the elements before the pivot element are less
than or equal to pivot element and after the pivot element are greater than or equal to the
pivot element.
Now, the same procedure is repeated on the elements before the pivot element as well
as on the elements after the pivot element.
When all passes are completed, then list of array elements are available in sorted
order.
Example: Sort the following elements using quick sort.
12 9 17 16 94
Pass 1:
K[1:5] 12 9 17 16 94
pivot = 12
i=1
j=6 1<6 TRUE
i=2 9 ≥ 12 FALSE
i=3 17 ≥ 12 TRUE
j=5 94 ≤ 12 FALSE
j=4 16 ≤ 12 FALSE
j=3 17 ≤ 12 FALSE
j=2
Here, i>j (3 > 2) TRUE
Interchange 9 & 12
K[1:5] = 9 12 17 16 94
K[1:1] K[3:5]
Pass 2:
K[3:5] = 17 16 94
pivot = 17
i =3
j=6 3<6 TRUE
i=4 16 ≥ 17 FALSE
i=5 94 ≥ 17 TRUE
j=5 94 ≤ 17 FALSE
j=4
Here, i>j (5 > 4) TRUE
Interchange 16 & 17
K[1:3] = 16 17 94
K[1:5] = 9 12 16 17 94
Sort list of elements are : 9 12 16 17 94
Example: Sort the following elements using quick sort.
76 92 11 24 49 33
ALGORITHM
QuickSort(K,LB,UB): Let K is an array that consists of ‘n’ elements from index 1 to
index n. Assume LB refers to the first index 1 and UB refers to the last index n at the
initial call. This procedure sorts the elements of K in ascending order..
Step 1: flag ← TRUE
Step 2: IF LB < UB THEN
i ← LB
j ← UB + 1
pivot ← K[LB]
Repeat WHILE flag
i ← i+1
Repeat WHILE K[i] < pivot
i ← i+1
EndRepeat
j ← j-1
Repeat WHILE K[j] > pivot
j ← j-1
EndRepeat
IF i < j THEN
Interchange K[i] and K[j] elements
ELSE
flag ← FALSE
ENDIF
EndRepeat
Interchange K[LB] and K[j] elements
Call QuickSort(K , LB , j-1)
Call QuickSort(K , j+1 , UB)
ENDIF
Step 3: RETURN
Program:
import [Link];
public class QuickSort {
// Swap function
static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
// Partition function: same logic as in the C program
static int partition(int[] arr, int low, int high) {
int pivot = arr[low];
int i = low;
int j = high;
while (i < j) {
while (i < high && arr[i] <= pivot)
i++;
while (arr[j] > pivot)
j--;
if (i < j)
swap(arr, i, j);
swap(arr, low, j);
return j;
// QuickSort recursive function
static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
public static void main(String[] args) {
int[] arr = {4, 2, 5, 3, 1};
quickSort(arr, 0, [Link] - 1);
[Link]("Sorted array: ");
for (int val : arr)
[Link](val + " ");
[Link]();
}
}
Analysis of Quick sort
1. The Worst case time complexity of quick sort is O (n2). It occurs when the list of
Worst case time complexity of Quick sort is O(n2) time.
2. The Average case time complexity of quick sort is O(n logn), which is less
compare to worst case time complexity.
The Average case time complexity of quick sort is O(n log n) time.
RECURSIVE MERGE SORT
Merge sort is also a sorting technique designed based on divide-and-conquer strategy.
Let K is an array that consists of ‘n’ elements from index 1 to index n. Sorting refers to the
process of rearranging the given elements of K in ascending order such that: K[1] ≤ K[2] ≤ . .
. . . . . . ≤ K[n].
In this sorting technique,
First divide the array elements into two sub arrays based on
Mid = (Low + High) / 2
Where,
Low is the first index of the array and High is the last index of the array.
Once, the sub arrays are formed, each set is individually sorted and the resulting sub
sequences are merged to produce a single sorted sequence of data elements.
Divide-and-Conquer strategy is applicable as splitting the array into sub arrays; and
combining operating is merging the sub arrays into a single sorted array.
Merging is the process of combining two sorted lists into a single sorted list. While
performing merging operation, the two sub lists must be in sorted order.
Example: Sort the following elements using merge sort.
12 9 17 16 94
Given k[1:5] = 12 9 17 16 94
Low = 1 High = 5 1<5 TRUE
Mid = (1+5)/2 = 3
Then, k[1:5] spitted into two sub arrays as: k[1:3] and k[4:5]
Consider k[1:3] = 12 9 17
Low = 1 High = 3 1<3 TRUE
Mid=(1+3)/2 = 2
Then, k[1:3] spitted into two sub array as: k[1:2] and k[3:3]
Consider k[1:2] = 12 9
Low = 1 High = 2 1<2 TRUE
Mid=(1+2)/2 = 1
Then, k[1:2] spitted into two sub array as: k[1:1] and k[2:2]
Apply Merge operation on k[1:1] and k[2:2], it produces a sorted list k[1:2] as
K[1:2] = 9 12
Apply Merge operation on k[1:2] and k[3:3], it produces a sorted list k[1:3] as
K[1:3] = 9 12 17
Consider k[4:5] = 16 94
Low = 4 High = 5 4<5 TRUE
Mid=(4+5)/2 = 4
Then, k[4:5] spitted into two sub array as: k[4:4] and k[5:5]
Apply Merge operation on k[4:4] and k[5:5], it produces a sorted list k[4:5] as
k[4:5] = 16 94
Apply Merge operation on k[1:3] and k[4:5], it produces a sorted list k[1:5] as
K[1:5] = 9 12 16 17 94
Sorted Elements Are: 9 12 16 17 94
ALGORITHM
MSort(Low, High): Let K is an array that consists of ‘n’ elements from index 1 to
index n. Low refers to the first index 1 and High refers to the last index n at the initial call.
This procedure sorts elements of K in ascending order.
Step 1: IF Low < High THEN
Mid ← (Low+High) / 2
Call MSort(Low,Mid)
Call MSort(Mid+1,High)
Call Merge(Low,Mid,High)
ENDIF
Step 2: RETURN
Merge(Low, Mid, High): This procedure merges the two sub sorted arrays into a single
sorted array.
Step 1: h ← Low
i ← Low
j ← Mid+1
Step 2: Repeat WHILE h ≤ Mid AND j ≤ High
IF K[h] ≤ K[j] THEN
S[i]←K[h]
h ← h+1
ELSE
S[i]←K[j]
j ← j+1
ENDIF
i ← i+1
EndRepeat
Step 3: IF h > Mid THEN
Repeat FOR p ← j TO High DO STEPS BY 1
S[i]←K[p]
i ←i+1
EndRepeat
ELSE
Repeat FOR p ← h TO Mid DO STEPS BY 1
S[i]←K[p]
i ←i+1
EndRepeat
ENDIF
Step 4: Repeat FOR p ← Low TO High DO STEPS BY 1
K[p] ← S[p]
EndRepeat
public class MergeSort
{
// Main function to perform merge sort
public void sort(int[] arr, int left, int right)
{
if (left < right)
{
// Find the middle point
int mid = (left + right) / 2;
// Recursively sort the first and second halves
sort(arr, left, mid);
sort(arr, mid + 1, right);
// Merge the sorted halves
merge(arr, left, mid, right);
}
}
// Merges two sub-arrays of arr[]
// First sub-array is arr[left..mid]
// Second sub-array is arr[mid+1..right]
private void merge(int[] arr, int left, int mid, int right)
{
// Find sizes of two sub-arrays to be merged
int n1 = mid - left + 1;
int n2 = right - mid;
// Create temporary arrays
int[] L = new int[n1];
int[] R = new int[n2];
// Copy data to temporary arrays
for (int i = 0; i < n1; ++i)
L[i] = arr[left + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[mid + 1 + j];
// Merge the temporary arrays back into arr[left..right]
int i = 0, j = 0; // Initial indexes of first and second sub-arrays
int k = left; // Initial index of merged sub-array
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
// Copy remaining elements of L[] if any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy remaining elements of R[] if any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
[Link]("Given Array:");
printArray(arr);
MergeSort ob = new MergeSort();
[Link](arr, 0, [Link] - 1);
[Link]("\nSorted Array:");
printArray(arr);
}
// Utility function to print an array
static void printArray(int[] arr)
{
for (int i = 0; i < [Link]; ++i)
[Link](arr[i] + " ");
[Link]();
}
}
Analysis of Merge Sort
Merge sort consists of several passes over the input. The first pass merges segments
of size1, second pass merges segments of size2, and the ith pass merges segments of size 2i-1.
Thus, the total number of passes is ┌ log 2n ┐.
At each pass, merge process required O(n) time. For ┌ log 2n ┐ passes, the total
computing time becomes O(n log n) time.
The Worst case and Average case time complexity of merge sort is O(n logn) time.