China
Africa
Explore chapters and articles related to this topic
Polynomial Time Algorithms
Published in Craig A. Tovey, Linear Optimization and Duality, 2020
Searching depends on the data structure used to hold the data set. One can often search an ordered set of n values in O(logn) time with a binary search algorithm. Binary search maintains two locations, v+ and v-, which are strict upper and lower bounds, respectively, on the location of the value being searched for. Check the value at location v=12(v++v−). If the desired value is not at location v, then v is either too high or too low. Update the upper or lower bound and repeat. This algorithm requires that the set be ordered but not that the value being searched for be present. Question: Why not?7 If the value is not present, binary search tells you where it would fit into the ordered set.
Development of Real-Time Software for Thomson Scattering Analysis at NSTX-U
Published in Fusion Science and Technology, 2019
Roman Rozenblat, Egemen Kolemen, Florian M. Laggner, Christopher Freeman, Greg Tchilinguirian, Paul Sichta, Gretchen Zimmer
Vector references are passed into functions; this is done to avoid copying the entire vector structure into the function’s working stack. All large array and vectors are allocated memory during the program initialization; therefore, each function and thread can access and store information in the vectors without allocating new memory. The unordered map data structure is used to access the corresponding values for each key in constant time. A binary search algorithm is used to efficiently search the corresponding voltage in a lookup vector. Since accessing the MDSplus tree is slow, all initialization parameters that are stored in the MDSplus tree are read and stored into vectors and unordered maps during program initialization. The program is compiled with the GNU Compiler Collection (GCC) compiler21 option of o3. With this option, the compiler optimizes the code for speed of execution. The program spends most of its time fitting the Thomson spectrum, i.e., calculating ne, Te, ne error, and Te error. We were able to reliably reduce the function execution time to 2.5 ms.
A novel hybrid combination optimization algorithm based on search area segmentation and fast Fourier transform
Published in Engineering Optimization, 2019
Fuqing Zhao, Guoqiang Yang, Yi Zhang, Wenchang Lei, Weimin Ma, Chuck Zhang
Binary search is an algorithm which search capability is outstanding and the time complexity is . The original binary algorithm divide the , which is an ascending sequence, to two part averagely. Comparing with the midpoint. If is equal to midpoint, the algorithm terminates. If smaller than midpoint while the left part as the search space at the next iterator, else the right search space will be selected. But the used binary search algorithm in this article is a little different from the original. So the modified binary search algorithm is described as follows.
Binarily Gapped Binary Insertion Sorting Technique
Published in IETE Journal of Research, 2018
Swapan Kumar Ray, Surajeet Ghosh
In the present paper, we propose a new kind of Insertion Sort, namely the Binarily Gapped Binary Insertion Sorting Technique (BGBIST), and describe its design and implementation. In this context, it may be noted that some preliminary work on the idea of binarily gapped binary insertion sort was done earlier and was presented in [4]. The BGBIST performs both the independent sub-tasks mentioned earlier that are needed for inserting a DE in a binary manner. For each arriving DE, the binary search algorithm (BSA) determines not only its relative position in the sorted array, stored in a random access memory (RAM), but also its absolute position (physical location) in the RAM. Actually, the arriving DEs are stored in the RAM by the BGBIST not only in a sorted order but also in a “binarily gapped” manner. As a result, the inter-DE gaps gradually reduce in size, broadly as a power of 2, with increasing occupancy of the RAM. This initial pattern of sorting without any movement of DEs continues for some time until “insertion collisions” start occurring, resulting in the beginning of “chain move” operations. The “chain move” operations resolve the collisions, still maintaining the sorted order. However, they disturb the initial binarily gapped feature of the insertions. Each linear movement chain terminates as soon as a gap is found and the arrived key is inserted. The movement chains become more and more frequent and their lengths become larger and larger as the gaps become rarer and rarer.