Tag Archives: sequential search

Computer Algorithms: Binary Search Tree

June 22, 2012algorithms, data structuresB-tree, balanced binary search tree, balanced binary search trees, binary search, Binary search tree, binary search trees, Binary trees, Environment, Extinction, ineffective binary search trees, Linked list, PHP, R-tree, Red-black tree, Scapegoat tree, search operation, search tree, search trees, sequential search, Technology/Internet, TreeStoimen

Introduction

Constructing a linked list is a fairly simple task. Linked lists are a linear structure and the items are located one after another, each pointing to its predecessor and its successor. Almost every operation is easy to code in few lines and doesn’t require advanced skills. Operations like insert, delete, etc. over linked lists are performed in a linear time. Of course on small data sets this works fine, but as the data grows these operations, especially the search operation becomes too slow.

Indeed searching in a linked list has a linear complexity and in the worst case we must go through the entire list in order to find the desired element. The worst case is when the item doesn’t belong to the list and we must check every single item of the list even the last one without success. This approach seems much like the sequential search over arrays. Of course this is bad when we talk about large data sets.

Search over Linked Lists and Arrays — Sequential search over arrays seems much like searching in linked lists and it is a basically ineffective opration!

Continue reading →

Computer Algorithms: Minimum and Maximum

May 21, 2012algorithmsApplication This algorithm, Calculus, comparisons solution, Counting sort, Mathematical analysis, Mathematical optimization, Maxima and minima, memory solution, Minima and maxima, Selection algorithm, sequential search, Sorting algorithms, The algorithmStoimen

Introduction

To find the minimum value into an array of items itsn’t difficult. There are not many options to do that. The most natural approach is to take the first item and to compare its value against the values of all other elements. Once we find a smaller element we continue the comparisons with its value. Finally we find the minimum.

First thing to note is that we pass through the array with n steps and we need exactly n-1 comparisons. It’s clear that this is the optimal solution, because we must check all the elements. For sure we can’t be sure that we’ve found the minimum (maximum) value without checking every single value.
Continue reading Computer Algorithms: Minimum and Maximum →

Computer Algorithms: Brute Force String Matching

March 27, 2012algorithmsAlgorithm, Bitap algorithm, Boyer–Moore string search algorithm, brute force algorithms, Computer science, Computing, Mathematics, PHP, pre-processing, search algorithms, sequential search, software development, String, String algorithms, string matching algorithm, String searching algorithm, Technology/Internet, text processing softwareStoimen

Introduction

String matching is something crucial for database development and text processing software. Fortunately every modern programming language and library is full of functions for string processing that help us in our everyday work. However is great to understand their principles.

String algorithms can be mainly divided into several categories. One of these categories is string matching.

When we come to string matching the most basic approach is what is known as brute force, which means just to check every single character from the text to match against the pattern. In general we have a text and a pattern (most commonly shorter than the text). What we need to do is to answer the question whether this pattern appears into the text.

Overview

The principles of brute force string matching are quite simple. We must check for a match between the first characters of the pattern with the first character of the text as on the picture bellow.

First step of brute force string matching — We start by comparing the first characters of the text and the pattern!

Continue reading →

Computer Algorithms: Insertion Sort

February 13, 2012algorithms, PHPAlgorithm, Application This algorithm, binary search, Insertion sort, Linear search, Merge sort, PHP, player, Quicksort, Selection sort, sequential search, Sort, Sorting algorithms, Strand sort, Technology/Internet, therefore sorting algorithms, typical algorithmStoimen

Overview

Sorted data can dramatically change the speed of our program, therefore sorting algorithms are something quite special in computer science. For instance searching in a sorted list is faster than searching in an unordered list.

There are two main approaches in sorting – by comparing the elements and without comparing them. A typical algorithm from the first group is insertion sort. This algorithm is very simple and very intuitive to implement, but unfortunately it is not so effective compared to other sorting algorithms as quicksort and merge sort. Indeed insertion sort is useful for small sets of data with no more than about 20 items.

Insertion sort it is very intuitive method of sorting items and we often use it when we play card games. In this case the player often gets an unordered set of playing cards and intuitively starts to sort it. First by taking a card, making some comparisons and then putting the card on the right position.

So let’s say we have an array of data. In the first step the array is unordered, but we can say that it consists of two sub-sets: sorted and unordered, where on the first step the only item in the sorted sub-set is its first item. If the length of the array is n the algorithm is considered completed in n-1 steps. On each step our sorted subset is growing with one item. The thing is that we take the first item from the unordered sub-set and with some comparisons we put it into its place in the sorted sub-set, like on the diagram bellow.

Continue reading →

Computer Algorithms: Binary Search

December 26, 2011algorithms, PHPAlgorithm, binary search, Binary search algorithm, Control flow, famous and best suitable search algorithm, Fibonacci number, Fibonacci search algorithm, Fibonacci search technique, Golden section search, golden section search algorithm, Jump search, Mathematics, PHP, Recursion, Recursion theory, recursive and iterative solution, search algorithm, search algorithms, sequential search, suitable search algorithm, Theoretical computer science, two algorithmsStoimen

Overview

The binary search is perhaps the most famous and best suitable search algorithm for sorted arrays. Indeed when the array is sorted it is useless to check every single item against the desired value. Of course a better approach is to jump straight to the middle item of the array and if the item’s value is greater than the desired one, we can jump back again to the middle of the interval. Thus the new interval is half the size of the initial one.

Binary search basic implementation — Basic implementation of binary search

If the searched value is greater than the one placed at the middle of the sorted array, we can jump forward. Again on each step the considered list is getting half as long as the list on the previous step, as shown on the image bellow.

Implementation

Here’s a sample implementation of this algorithm on PHP. Obviously the nature of this approach is guiding us to a recursive implementation, but as we know, sometimes recursion can be dangerous. That’s why here we can see either the recursive and iterative solution. Continue reading Computer Algorithms: Binary Search →

stoimen's web log

on web development

Tag Archives: sequential search

Computer Algorithms: Binary Search Tree

Introduction

Computer Algorithms: Minimum and Maximum

Introduction

Computer Algorithms: Brute Force String Matching

Introduction

Overview

Computer Algorithms: Insertion Sort

Overview

Computer Algorithms: Binary Search

Overview

Implementation