CourseWork of Data Structures and Algorithm

1. Explain: a) Linear search technique using an algorithm

b)Binary Search technique using an algorithm
c)Compare both

Analyze and compare linear search and binary search techniques, detailing the
algorithms and their efficiencies.

1. Introduction
Search algorithms are an essential part of computer science and algorithmic
studies. Fundamentally, these algorithms aim to identify the position of a target
value within a specified set of data. Among the numerous searching techniques
available, linear search and binary search stand out as two of the most widely
employed. Comparing these methods in terms of complexity offers practical insights
valuable at the academic level. In linear search, the algorithm sequentially
evaluates each element until it encounters the target, resulting in an average time
complexity that scales linearly with the size of the collection. Binary search,
applicable exclusively to sorted datasets, utilizes a divide-and-conquer strategy
by repeatedly halving the search interval, thereby achieving a logarithmic time
complexity. Nonetheless, linear search retains utility in scenarios where datasets
are small or unsorted, situations in which the overhead of sorting a collection is
unwarranted (Nguyen, 2012). The current investigation therefore undertakes a
comparative analysis of the linear and binary search algorithms, emphasizing their
respective complexities and situational applicability.
– 1.1 Overview of Search Techniques
Search techniques are algorithms used to locate a specific item within a data
structure. These methods are fundamental to computer science and programming, as
they form the basis for many applications, from retrieving a file on a computer to
finding a specific record in a large database. The choice of which search algorithm
to use depends on factors like the data's size and whether it's sorted, with each
method offering a unique trade-off between simplicity and speed (Cormen et al.,
2009).
– 1.2 Importance of Search Algorithms
Search algorithms are crucial because they directly impact the efficiency and
performance of a system. An inefficient search on a large dataset can lead to slow
response times, consuming excessive computational resources. Conversely, a well-
chosen search algorithm can provide near-instantaneous results, even with massive
amounts of data. Understanding these algorithms is a core skill for any programmer
or data scientist, as it allows them to design and implement solutions that are not
only correct but also scalable and performant. This importance is a key reason why
search and sorting algorithms are foundational topics in computer science education
(Knuth, 1998).

2. Linear Search Technique

– 2.1 Definition of Linear Search
Linear search, also known as sequential search, is a straightforward algorithm used
to find a target value within a list or array. It works by checking each element
one by one, in order, from the beginning of the list until the target is found or
the end is reached. This method is simple to understand and implement and doesn't
require the data to be sorted.
– 2.2 Algorithm for Linear Search
▪ 2.2.1 Step-by-Step Explanation
Imagine you have a row of mailboxes and you are looking for a letter with a
specific name. A linear search is like checking each mailbox, one after another,
until you find the correct name.
The process is as follows:
* Start at the first element in the list (index 0).
 * Compare the element at the current index to the target value.
* If they are a match, the search is successful. You've found the item. Return the
current index.
* If they don't match, move to the next element in the list.
* Repeat steps 2-4 until a match is found or you have checked every element.
* If you reach the end of the list without finding the target, the search is
unsuccessful.
▪ 2.2.2 Pseudocode Example
FUNCTION linearSearch(array, target_value):
FOR index FROM 0 TO LENGTH(array) - 1:
IF array[index] IS EQUAL TO target_value:
RETURN index // Target found at this index
END FOR
RETURN -1 // Target not found in the array
– 2.3 Time Complexity of Linear Search
The time complexity of an algorithm describes how its runtime grows as the input
size increases. For linear search, the time complexity is typically expressed using
Big O notation (O).
* Best-Case Time Complexity: O(1). This occurs when the target element is the very
first item in the list. The algorithm finds the target in a single step, making it
extremely fast.
* Worst-Case Time Complexity: O(n). This happens when the target element is the
last item in the list or is not present in the list at all. In these cases, the
algorithm has to check every single element (n) to confirm its presence or absence.
* Average-Case Time Complexity: O(n). On average, the algorithm will have to check
about half of the elements in the list to find the target. Since n/2 is still
proportional to n, the average case is also represented as O(n).
In short, the performance of a linear search is directly proportional to the size
of the list. A list with 1,000 items could take up to 1,000 comparisons.

3. Binary Search Technique

– 3.1 Definition of Binary Search
Binary search is a highly efficient algorithm for finding an element within a
sorted list. Unlike linear search, it doesn't check every item. Instead, it works
on the principle of "divide and conquer" by repeatedly cutting the search space in
half until the target is found or the search space is exhausted.
– 3.2 Algorithm for Binary Search
▪ 3.2.1 Step-by-Step Explanation
Imagine you're trying to find a specific word in a dictionary. You don't start at
the first page and go through every word. Instead, you open to the middle. If your
word comes after the words on that page, you discard the first half of the book and
repeat the process on the second half. This is the essence of binary search.
The process is as follows:
* Establish a search range using two pointers: a low pointer at the first index
and a high pointer at the last index of the sorted list.
* While the low pointer is less than or equal to the high pointer, continue the
search.
* Calculate the middle index (mid) of the current search range using the formula:
mid = (low + high) / 2.
* Compare the element at the mid index with the target value.
* If the element at mid is the target, the search is successful. Return the mid
index.
* If the element at mid is less than the target, it means the target must be in
the right half of the list. Update the low pointer to mid + 1 to discard the left
half.
* If the element at mid is greater than the target, the target must be in the left
half of the list. Update the high pointer to mid - 1 to discard the right half.
* If the loop completes without finding the target (i.e., low becomes greater than
high), the target is not in the list.
 ▪ 3.2.2 Pseudocode Example
FUNCTION binarySearch(sorted_array, target_value):
low = 0
high = LENGTH(sorted_array) - 1

WHILE low <= high:

mid = FLOOR((low + high) / 2)

IF sorted_array[mid] IS EQUAL TO target_value:

RETURN mid // Target found

ELSE IF sorted_array[mid] < target_value:

low = mid + 1 // Search the right half

ELSE:
high = mid - 1 // Search the left half

END WHILE

RETURN -1 // Target not found

– 3.3 Time Complexity of Binary Search
The time complexity of binary search is O(\\log n). This logarithmic complexity is
why binary search is so much faster than linear search for large datasets. At each
step, the algorithm reduces the search space by half.
Let's illustrate why:
* In the first step, the search space has size n.
* After one comparison, the search space is reduced to n/2.
* After two comparisons, it's reduced to n/4.
* After k comparisons, the search space is n/2^k.
The search is complete when the search space is narrowed down to a single element,
meaning n/2^k \\approx 1. To solve for the number of steps (k), we can take the
logarithm: 2^k \\approx n \\implies k \\approx \\log\_2 n.
* Best-Case Time Complexity: O(1). This occurs when the target is the very first
element checked—the middle element of the original list.
* Worst-Case Time Complexity: O(\\log n). This happens when the target is at one
of the ends of the list or not in the list at all. The algorithm must repeatedly
halve the list until the search space is reduced to nothing.
* Average-Case Time Complexity: O(\\log n). On average, the number of comparisons
is proportional to the logarithm of the list size.

4. Comparison of Linear Search and Binary Search

– 4.1 Efficiency and Performance
The key difference between linear and binary search lies in their time complexity,
which measures their performance as the input size (n) grows.
* Linear Search: Has a time complexity of O(n). In the worst case, it has to check
every single element in the list. This means if you double the number of items in
the list, you can expect the search time to roughly double as well.
* Binary Search: Has a time complexity of O(\\log n). This is significantly more
efficient. With each step, it cuts the search space in half. This means that a
list with a million items can be searched in about 20 steps (\\log\_2 1,000,000 \\
approx 19.9). Doubling the number of items in a binary search only adds one more
step. This makes it an ideal algorithm for large datasets (Sedgewick & Wayne,
2011).
– 4.2 Use Cases and Applications
* Linear Search:
* Unsorted Data: This is its primary use case. Since linear search doesn't
require the data to be in any specific order, it's the only option if sorting the
data is not feasible or necessary.
* Small Datasets: For very small lists (e.g., fewer than 50 items), the
performance difference between linear and binary search is negligible. The
simplicity of linear search often makes it a better choice in these situations.
* Binary Search:
* Sorted Data: Binary search is used extensively in applications where data is
already sorted or can be sorted efficiently.
* Databases and File Systems: It's a foundational technique used in database
indexing and file system searches to quickly locate records.
* Lookups: Anytime you need to perform quick lookups on a large, ordered
collection, such as finding a name in a directory or a product in a large
inventory.
– 4.3 Advantages and Disadvantages
| Feature | Linear Search | Binary Search |
|---|---|---|
| Advantages | * Works on unsorted data. <br/> * Simple and easy to implement.
<br/> * Requires minimal setup. | * Extremely fast for large datasets. <br/> *
Highly efficient (O(\\log n)). <br/> * Scales well with large data. |
| Disadvantages | * Slow for large datasets. <br/> * Inefficient for sorted data.
<br/> * Can be too slow for real-time applications with large inputs. | * Requires
the data to be sorted. <br/> * The cost of sorting can outweigh the benefit if the
data is searched only once. <br/> * More complex to implement than linear search. |

5. Conclusion

5.2 Final Thoughts on Choosing the Right Search Technique

– 5.1 Summary of Key Points

Linear and binary search are two fundamental algorithms for finding a specific
element in a collection of data. The primary distinction between them lies in their
approach and efficiency. Linear search is a simple, brute-force method that checks
every element sequentially. It's easy to implement and works on any list,
regardless of whether it's sorted. However, its efficiency is poor, with a time
complexity of O(n), making it unsuitable for large datasets.
In contrast, binary search is a highly efficient algorithm with a time complexity
of O(\log n). It works by repeatedly dividing the search space in half, which
drastically reduces the number of comparisons. This speed comes at a cost: binary
search requires the data to be sorted beforehand.
– 5.2 Final Thoughts on Choosing the Right Search Technique
Choosing the right search technique is a trade-off between simplicity and
performance.
* Use linear search when:
* The list is small.
* The data is unsorted, and the cost of sorting is too high or unnecessary.
* You only need to perform a search a few times.
* Use binary search when:
* The list is large.
* The data is already sorted or will be searched many times, justifying the one-
time cost of sorting.
* Performance is a critical factor.
In essence, if you need a quick and dirty solution for an unsorted list, linear
search is the way to go. If you're working with a large, sorted dataset where every
millisecond counts, binary search is the superior and more intelligent choice.

6. References
– 6.1 Suggested Readings
* Nguyen, P., 2012. Combinatorial Spaces And Order Topologies from
https://arxiv.org/pdf/1209.1060
* Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction
to Algorithms (3rd ed.). The MIT Press.
* Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and
Searching (2nd ed.). Addison-Wesley Professional.
* Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley
Professional.

– 6.2 Online Resources

* Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction
to Algorithms (3rd ed.). The MIT Press.
* Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley
Professional.
* Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and
Searching (2nd ed.).
6.2 Online Resources
* GeeksforGeeks.
* Khan Academy.
* HackerRank.

————————————————————————
2. Write the code for the following functions: a)peek()
b)push()
c)pop()
d)isFull()
e)isEmpty()

▎Table of Contents

1. Introduction
– 1.1 Overview of Stack Data Structure
– 1.2 Importance of Stack Operations

2. Stack Operations
– 2.1 Definition of Stack Operations
– 2.2 Common Use Cases for Stack Operations

3. Function Implementations
– 3.1 peek() Function
▪ 3.1.1 Definition and Purpose
▪ 3.1.2 Code Implementation
▪ 3.1.3 Example Usage
– 3.2 push() Function
 ▪ 3.2.1 Definition and Purpose
▪ 3.2.2 Code Implementation
▪ 3.2.3 Example Usage
– 3.3 pop() Function
▪ 3.3.1 Definition and Purpose
▪ 3.3.2 Code Implementation
▪ 3.3.3 Example Usage
– 3.4 isFull() Function
▪ 3.4.1 Definition and Purpose
▪ 3.4.2 Code Implementation
▪ 3.4.3 Example Usage
– 3.5 isEmpty() Function
▪ 3.5.1 Definition and Purpose
▪ 3.5.2 Code Implementation
▪ 3.5.3 Example Usage

4. Conclusion
– 4.1 Summary of Stack Functions
– 4.2 Final Thoughts on Stack Operations

5. References
– 5.1 Suggested Readings on Stack Data Structure
– 5.2 Online Resources for Further Learning