Search – Python, Data structures, OOPS, Big O

Searching and Sorting Algorithms

Posted on March 14, 2020June 5, 2020 by Naveen

Searching Algorithms : Linear SearchBinary SearchJump SearchInterpolation SearchExponential SearchSublist Search (Search a linked list in another list)Fibonacci SearchThe Ubiquitous Binary SearchRecursive program to linearly search an element in a given arrayRecursive function to do substring searchUnbounded Binary Search Example (Find the point where a monotonically increasing function becomes positive first time) Sorting Algorithms: Selection SortBubble … Continue reading Searching and Sorting Algorithms

Fibonacci Search

Posted on September 24, 2019 by Naveen

Fibonacci Search is a comparison-based technique that uses Fibonacci numbers to search an element in a sorted array. Similarities with Binary Search: Works for sorted arrays A Divide and Conquer Algorithm. Has Log n time complexity. Differences with Binary Search: Fibonacci Search divides given array in unequal partsBinary Search uses division operator to divide range. … Continue reading Fibonacci Search

Exponential Search

Posted on September 13, 2019September 24, 2019 by Naveen

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

Posted on September 11, 2019September 11, 2019 by Naveen

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

Posted on September 11, 2019 by Naveen

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

Posted on September 11, 2019September 11, 2019 by Naveen

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