Searching and Sorting Algorithms

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

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

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

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