Tag Archives: Theoretical computer science

Computer Algorithms: Binary Search

algorithms, PHP, , , , , , , , , , , , , , , , , , , , ,

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.

Binary search - basic implementation
Binary search - basic implementation

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 →

Friday Algorithms: Input Data and Complexity

algorithms, web development, , , , , , , , ,

Size of ..

As we all know most of the cases a program execution time depends most from the input data. As I wrote in my post the degree of the input data estimates the algorithm complexity.

Of course 3*n² is a bit faster than 5*n², but in general both functions are similar and have the same complexity. In this case we tend to say that the size of the input data is n.

Size of the input data
The size of the input data affects the complexity of the algorithm

It is easy to bind this to arrays or other simple data structures. For example when sorting an array with n elements, the size of the input data is n, but sometimes there is not such an obvious relation between an algorithm and the size of the input data.

For instance when we’ve to search a path into a graph, than maybe the best way to describe the input data is by summing both the number of vertices and the number of edges.

Conclusion

Think, think, think
Think, think, think

However this is important when dealing with algorithms, because a mistake in the estimation of the input data size will result in wrong algorithm estimation at all

Bind Zend Action with Non-Default View

micro tutorial, PHP, zend framework, , ,

Action – View

You may know that every controller’s action in Zend Framework has to be bind to a view. Normally you can disable the view for a specific action, but how about “forking” an action to render different views?!

In example when some _GET parameter is set redirect to another view? That’s rather strange and perhaps there’s a clear and yet full MVC solution! First of all you can setup all of the view variables simply in the “parent” action.

<?php
 
class IndexController extends Zend_Controller_Action
{
	public function indexAction()
	{
		$this->view->title = 'This is the default action!';	
	}
}

Than the view file will contain something like:

// index/index.phtml
<h1><?php echo $this->title ?></h1>

Than whenever you have the given _GET set you can _forward to another action (perhaps with no code at all) and only a different view. Thus you don’t setup twice the view variables.

<?php
 
class IndexController extends Zend_Controller_Action
{
	public function indexAction()
	{
		$this->view->title = 'This is the default action!';	
 
		if (isset($_GET['my_param'])) {
			$this->_forward('another');
		}
	}
 
	public function anotherAction()
	{}
}

And there are two views practically for one action:

// index/index.phtml
<h1><?php echo $this->title ?></h1>
 
// index/another.phtml
<h2><?php echo $this->title ?></h2>