Easy and Efficient Programming for Contests - Exploiting the language's strengths
(Page 4 of 4 )
Now we already know that every language has its strengths and weaknesses. As for the C/C++ world, it is a known truth that bitwise operations are much faster than the usual ones known from math classes. Here I will present a method that uses this knowledge to work approximately four times faster than the ones presented in manuals.
The original idea came from Mihai Patrascu, and we are talking about binary search. This type of search will find an item inside a sorted array, taking advantage of the fact that the array is sorted. It will always split the array into two, determine in which part of it is our value, and repeat for that section the upper algorithm until it finds it. The algorithm I will present here will follow this idea, however, by comparing the values directly it will start to determine bit by bit the queried value:
#include "stdio.h"
#include "stdlib.h"
int length;
int *array;
int binary_search(int value)
{
int i, step;
for (step = 1; step < length; step <<= 1);
for (i = 0; step; step >>= 1)
if (i + step < length && array[i + step] <= value)
i += step;
return i;
}
During the first step it determines how many moves it needs to make, or in more common language, calculates log 2 length. In the second step, it takes the route back and adjusts “i” until it finds the element.
For now we will take a break so you can digest what I've presented here so far. I leave you with the promise that next week I will finish up this series of articles with the fourth part.
Moreover, until then I also invite you to share your thought either here on the article's blog or in the forums for DevArticles and DevHardware . Joining costs nothing except a little time from you, and you will enter a community with which you can talk about your problems. Feel free to act. Until next time, Live With Passion!
| DISCLAIMER: The content provided in this article is not warranted or guaranteed by Developer Shed, Inc. The content provided is intended for entertainment and/or educational purposes in order to introduce to the reader key ideas, concepts, and/or product reviews. As such it is incumbent upon the reader to employ real-world tactics for security and implementation of best practices. We are not liable for any negative consequences that may result from implementing any information covered in our articles or tutorials. If this is a hardware review, it is not recommended to open and/or modify your hardware. |
