Sublist search is used to detect a presence of one list in another list. Suppose we have a single-node list (let's say the first list), and we want to ensure that the list is present in another list (let's say the second list), then we can perform the sublist search to find it. For instance, … Continue reading Sublist Search-(Search a linked list in another list)
Exponential Search
Exponential search is an algorithm used for searching sorted, unbounded/infinite arrays. The idea is to determine a range that the target value resides in and perform a Binary Search within that range. Assuming that the array is sorted in ascending order, it looks for the first exponent k, where the value 2k is greater than the search … Continue reading Exponential Search
Interpolation Search
The Interpolation Search is an improvement over Binary Search for instances, where the values in a sorted array are uniformly distributed. Binary Search always goes to the middle element to check. On the other hand, interpolation search may go to different locations according to the value of the key being searched. For example, if the … Continue reading Interpolation Search
Jump Search
The basic idea is to check fewer elements (than linear search) by jumping ahead by fixed steps or skipping some elements in place of searching all elements. Important points Works only sorted arrays.The optimal size of a block to be jumped is (√ n). This makes the time complexity of Jump Search O(√ n).The time … Continue reading Jump Search
Search Algorithm
Searching Algorithms are designed to check for an element or retrieve an element from any data structure where it is stored. Based on the type of search operation, these algorithms are classified into 2 categories: Sequential Search: the list or array is traversed sequentially and every element is checked. For Ex: Linear Search.Interval Search: These … Continue reading Search Algorithm
Guide to Big O Notation
We’ve all heard of Big(O). It’s something most of us learn in college and promptly forget. We also know it’s something that Top Coders and Googlers are good at and many of us would like to be good at it too! I can relate – I find many algorithms fascinating and many more intimidating. And for a long time I struggled to get my head around the concept of Big(O). I knew what it was – vaguely – but I had no deep understanding – no intuition for it at all. And I knew that it was important in telling me which algorithms were good and which weren’t. If you can relate to that then this article is for you – you will be able to understand Big(O) and have the beginnings of an intuition about it.
Python, Data structures, OOPS, Big O 