Meta tags:
Headings (most frequently used words):
search, binary, procedure, of, performance, other, notes, alternative, for, finding, the, element, searches, contents, algorithm, versus, schemes, variations, history, implementation, issues, library, support, see, also, and, references, external, links, duplicate, elements, approximate, matches, space, complexity, derivation, average, case, additional, considerations, linear, trees, hashing, set, membership, algorithms, data, structures, uniform, exponential, interpolation, fractional, cascading, generalization, to, graphs, noisy, quantum, citations, sources, leftmost, rightmost, successful, unsuccessful, cost, comparison, branch, prediction, cache, usage,
Text of the page (most frequently used words):
the (665), #search (250), #binary (172), displaystyle (169), and (131), for (125), log (118), array (77), element (75), that (74), target (60), are (54), this (53), can (49), with (45), case (45), edit (44), value (44), algorithm (42), elements (39), from (38), tree (38), than (38), average (38), searching (37), path (34), arrays (33), textstyle (33), procedure (32), lfloor (32), rfloor (32), knuth (31), number (29), sorted (29), which (29), doi (28), time (27), each (27), iteration (27), length (26), may (25), set (25), data (24), iterations (24), when (24), algorithms (23), 2016 (23), 1998 (22), trees (22), one (22), frac (22), internal (22), where (22), middle (22), two (21), external (20), worst (20), table (19), all (19), subsection (19), comparison (19), there (19), other (19), not (19), isbn (18), retrieved (18), function (18), searches (18), such (18), archived (17), computer (17), ordered (17), node (17), only (17), structures (16), comparisons (16), 978 (16), queries (16), linear (16), nodes (16), used (16), equal (16), finding (15), hash (15), has (15), original (15), range (15), fractional (15), cascading (15), interpolation (15), more (15), less (15), left (15), return (15), example (14), pdf (14), performance (14), then (14), position (14), right (14), unsuccessful (14), root (13), 1145 (13), acm (13), while (13), searched (13), approximate (13), most (13), faster (13), floor (13), wikipedia (12), index (12), programming (12), first (12), standard (12), library (12), april (12), half (12), its (12), because (12), keys (12), same (12), however (12), was (11), list (11), implementation (11), quantum (11), lower (11), but (11), complexity (11), successful (11), also (11), matches (11), method (10), integers (10), s2cid (10), performed (10), any (10), every (10), uniform (10), efficiently (10), comparing (10), integer (10), using (9), published (9), upper (9), large (9), java (9), problem (9), space (9), based (9), some (9), article (9), values (9), given (9), would (9), makes (9), bit (9), above (9), about (8), use (8), articles (8), science (8), sorting (8), wesley (8), 2011 (8), march (8), computing (8), sum (8), noisy (8), hashing (8), rank (8), possible (8), requires (8), likely (8), within (8), require (8), vertex (8), next (8), operations (8), usually (8), membership (8), memory (8), rightmost (8), else (8), toggle (7), page (7), implementations (7), version (7), bounds (7), tables (7), order (7), deletion (7), functions (7), specific (7), key (7), will (7), lengths (7), paths (7), into (7), midpoint (7), provides (7), matching (7), whether (7), instead (7), main (7), between (7), exponential (7), they (7), equation (7), leftmost (7), access (6), 4th (6), addison (6), professional (6), wayne (6), sedgewick (6), vol (6), bentley (6), type (6), 2018 (6), journal (6), probability (6), bloom (6), history (6), paul (6), predecessor (6), contains (6), structure (6), these (6), bits (6), point (6), both (6), end (6), equally (6), plus (6), must (6), levels (6), similar (6), logarithm (6), another (6), insertion (6), loop (6), even (6), exactly (6), always (6), done (6), perform (6), smallest (6), largest (6), logarithmic (6), level (6), leq (6), additional (5), pseudocode (5), errors (5), links (5), binary_search (5), 2019 (5), 2002 (5), 2008 (5), michael (5), rust (5), sort (5), base (5), information (5), june (5), extra (5), chazelle (5), bernard (5), arxiv (5), symposium (5), theory (5), fast (5), optimal (5), graphs (5), variation (5), problems (5), khuong (5), lists (5), support (5), constant (5), result (5), initial (5), over (5), after (5), does (5), notes (5), solve (5), performing (5), returned (5), once (5), failed (5), found (5), size (5), very (5), store (5), correct (5), power (5), representing (5), least (5), exact (5), compare (5), find (5), works (5), greater (5), much (5), efficient (5), required (5), alternative (5), successor (5), contents (4), terms (4), foundation (4), short (4), peer (4), reviewed (4), graph (4), language (4), andrew (4), 1007 (4), 201 (4), donald (4), 1997 (4), 2006 (4), press (4), goldman (4), 2003 (4), std (4), 1016 (4), 1986 (4), known (4), october (4), 2022 (4), well (4), issn (4), higher (4), should (4), related (4), caches (4), branch (4), common (4), lowest (4), representation (4), takes (4), units (4), computation (4), slightly (4), represented (4), yields (4), out (4), children (4), lie (4), divided (4), their (4), since (4), record (4), numbers (4), floating (4), strings (4), implemented (4), although (4), addition (4), check (4), checks (4), often (4), wrong (4), cases (4), per (4), few (4), computers (4), certain (4), stored (4), either (4), otherwise (4), taking (4), best (4), close (4), variations (4), records (4), nearest (4), schemes (4), being (4), count (4), itself (4), ram (4), locations (4), child (4), reached (4), deepest (4), greatest (4), duplicate (4), hide (4), move (4), sidebar (4), languages (3), view (3), text (3), available (3), under (3), inc (3), august (3), open (3), wayback (3), different (3), wikidata (3), wikijournal (3), associative (3), dictionary (3), 2013 (3), book (3), reading (3), art (3), combinatorial (3), reference (3), 2000 (3), python (3), bisection (3), apple (3), mac (3), developer (3), binarysearch (3), util (3), package (3), cobol (3), bsearch (3), july (3), read (3), algorithmica (3), guibas (3), leonidas (3), tricks (3), proceedings (3), applied (3), analysis (3), random (3), quant (3), via (3), years (3), error (3), system (3), 2001 (3), communications (3), exercise (3), cuckoo (3), filter (3), judy (3), methods (3), minimum (3), lisp (3), eliminates (3), derivation (3), bottenbruch (3), hermann (3), 1962 (3), interval (3), simply (3), location (3), highest (3), designed (3), mix (3), running (3), cost (3), represent (3), therefore (3), present (3), applies (3), follows (3), notation (3), content (3), references (3), idea (3), see (3), framework (3), collection (3), respectively (3), ranges (3), many (3), made (3), indices (3), calculating (3), overflow (3), twenty (3), part (3), whose (3), until (3), numerous (3), computational (3), geometry (3), work (3), bounded (3), cannot (3), pair (3), been (3), types (3), generalization (3), queried (3), located (3), finds (3), multiple (3), pointers (3), second (3), small (3), way (3), near (3), account (3), visualization (3), stores (3), difference (3), current (3), specialized (3), take (3), long (3), regardless (3), encoding (3), filters (3), like (3), single (3), balanced (3), except (3), unlike (3), versus (3), tlb (3), accessed (3), cache (3), assuming (3), substituting (3), added (3), intervals (3), outside (3), reaches (3), neighbor (3), following (3), ceiling (3), continues (3), tools (3), topic (2), code (2), contact (2), privacy (2), policy (2), apply (2), organization (2), wikimedia (2), commons (2), license (2), last (2), 2026 (2), categories (2), date (2), dates (2), description (2), literature (2), org (2), string (2), dynamic (2), divide (2), conquer (2), linked (2), machine (2), september (2), saddle (2), river (2), new (2), jersey (2), 321 (2), stroustrup (2), robert (2), moffat (2), turpin (2), academic (2), coding (2), 2nd (2), 3rd (2), kasahara (2), morishita (2), college (2), sequence (2), processing (2), practical (2), fitzgerald (2), 2015 (2), ruby (2), 2009 (2), rivest (2), ronald (2), cormen (2), chang (2), shi (2), software (2), engineering (2), butterfield (2), ngondi (2), 7th (2), oxford (2), university (2), pearls (2), jon (2), sources (2), 2024 (2), primitive (2), slice (2), bisect (2), nsarray (2), microsoft (2), oracle (2), corporation (2), platform (2), edition (2), documentation (2), collections (2), manual (2), group (2), letters (2), research (2), 1988 (2), applications (2), technique (2), help (2), cite (2), lehmer (2), derrick (2), 1960 (2), 0113289 (2), 1957 (2), storage (2), peterson (2), william (2), grover (2), 032335 (2), review (2), rényi (2), magyar (2), pelc (2), andrzej (2), 3975 (2), theoretical (2), coping (2), 10th (2), meyer (2), 221 (2), probabilistic (2), liu (2), ding (2), jcss (2), sciences (2), intersection (2), dimension (2), conference (2), better (2), techniques (2), morin (2), pat (2), disks (2), symbol (2), what (2), answers (2), pvk (2), 2017 (2), 23752485 (2), mispredictions (2), implement (2), further (2), algol (2), 1971 (2), citations (2), exist (2), improve (2), have (2), ordinary (2), sentinel (2), mod (2), his (2), model (2), regular (2), grows (2), slowly (2), existing (2), compares (2), adding (2), minimized (2), minimizes (2), linearly (2), subtree (2), parent (2), big (2), factor (2), simplified (2), real (2), class (2), built (2), module (2), keeps (2), offers (2), static (2), classes (2), general (2), exit (2), conditions (2), defined (2), failure (2), programmers (2), variables (2), course (2), solution (2), several (2), incorrect (2), run (2), furthermore (2), own (2), contained (2), edge (2), straightforward (2), issues (2), worked (2), increasing (2), developed (2), back (2), tablet (2), names (2), were (2), classical (2), still (2), runs (2), 605 (2), approx (2), 433 (2), make (2), considered (2), tau (2), generalized (2), learns (2), undirected (2), positively (2), weighted (2), similarly (2), edges (2), subtrees (2), speeds (2), slower (2), extends (2), unbounded (2), bound (2), beforehand (2), subarray (2), adds (2), change (2), systems (2), inefficient (2), lookup (2), attribute (2), efficiency (2), ability (2), results (2), specifically (2), useful (2), themselves (2), filesystems (2), resulting (2), worse (2), fewest (2), including (2), simple (2), determining (2), cpu (2), cam (2), address (2), typical (2), four (2), smaller (2), processor (2), along (2), making (2), jump (2), usage (2), according (2), expressed (2), prediction (2), forms (2), consideration (2), increase (2), unsigned (2), expensive (2), considerations (2), reduced (2), called (2), doing (2), during (2), unique (2), positive (2), below (2), three (2), assumed (2), ends (2), here (2), 100 (2), ranks (2), endpoints (2), compute (2), equals (2), 5th (2), ceil (2), now (2), terminates (2), leave (2), eliminated (2), step (2), remaining (2), appearance (2), upload (2), file (2), changes (2), english (2), create (2), donate (2), menu (2), add, mobile, cookie, statement, statistics, developers, conduct, legal, safety, contacts, disclaimers, site, you, agree, registered, trademark, non, profit, creative, attribution, sharealike, rendered, parsoid, edited, utc, hidden, incorporating, publications, cs1, webarchive, template, dmy, featured, w2j, externally, https, php, title, oldid, 1371884285, topological, sweep, line, streaming, recursion, randomized, online, minimax, greedy, fold, traversal, depth, brute, force, breadth, backtracking, algorithmic, paradigms, trie, stack, segment, queue, heap, fenwick, benchmarks, variety, nist, wikibook, 56384, bjarne, condensed, web, kevin, 57351, alistair, hamburg, germany, kluwer, publishers, 7923, 7668, 4615, 0935, compression, 1st, 03804, 89685, 89683, fundamental, masahiro, shinichi, london, imperial, 86094, 635, scale, genome, kenneth, boca, raton, florida, 58488, 455, crc, guide, sally, sebastopol, california, 4919, 2601, reilly, media, pocket, mit, mcgraw, hill, 262, 03384, introduction, stein, clifford, leiserson, charles, thomas, kuo, knowledge, singapore, 981, 238, 348, world, scientific, gerard, 968897, 65788, 152, cfarray, network, 2012, 601, 598, ansi, unisys, 2020, dlang, 945, specifications, principles, ruggieri, salvatore, s0020, 0190, 00263, semi, google, blog, nearly, mergesorts, broken, bloch, joshua, textbook, 194, 52965, 53012, 190, sigcse, bulletin, pattis, richard, challenge, 191, 11232235, bf01840441, 163, 162, 12745042, bf01840440, 133, structuring, incompatibility, teaching, symposia, mathematics, 181, 9780821813102, 1090, psapm, 010, 180, a000225, oeis, addressing, 146, 1147, 0130, 130, ibm, development, 1996, 28th, philadelphia, 219, 237814, 237866, 9605043, 212, mechanical, database, lov, childs, landahl, parrilo, pablo, 2007, semidefinite, 41539957, 1103, physreva, 2007phrva, 75c2335c, bibcode, 0608161, physical, høyer, peter, neerbek, jan, yaoyun, complexities, distinctness, 448, 13717616, s00453, 002, 0976, 0102078, 429, alfréd, 1961, 516, 0143666, 515, tudományos, akadémia, matematikai, kutató, intézetének, közleményei, 109, s0304, 00303, 270, games, fifty, liars, winklmann, 800133, 804351, procedures, kleitman, daniel, albert, 1989, 202, 0304, 90077, 185, ben, hassidim, avinatan, 230, 7695, 3436, 1109, focs, 49th, foundations, bayesian, learner, pretty, good, emamjomeh, zadeh, ehsan, kempe, david, singhal, vikrant, 48th, 532, 2897518, 2897656, 1503, 00805, 519, deterministic, 2004, 284, 0022, 0000, 003, 269, 33rd, 329, 58113, 349, 380752, 380818, 322, perl, yehoshua, itai, alon, avni, haim, 1978, 553, 11089655, 359545, 359557, 550, important, burton, 1970, trade, offs, allowable, 426, 7931252, 362686, 362692, 422, fan, bin, andersen, dave, kaminsky, mitzenmacher, 2014, international, emerging, networking, experiments, technologies, 2674005, 2674994, practically, silverstein, alan, hewlett, packard, shop, bitwise, dietzfelbinger, martin, auf, der, heide, friedhelm, rohnert, hans, 1994, perfect, 761, 1137, s0097539791194094, 738, siam, tarjan, mehlhorn, kurt, karlin, anna, multiway, drums, exercises, beame, 1006, 1822, fich, faith, sequential, allocation, pathological, virak, layouts, 3053370, 1509, 05053, experimental, algorithmics, relevant, quotations, ieee, 754, pun, explanation, github, total_cmp, f32, f64, golddranks, pull, request, 72568, lang, herf, december, stereopsis, graphics, radix, rolfe, timothy, 289251, 289255, signum, newsletter, analytic, 169, theorem, 461, 463, selection, bibliography, described, 214, titled, program, 13406983, 0004, 5411, 321119, 321120, 161, flores, ivan, madpis, george, 603, 43325465, 0001, 0782, 362663, 362752, 602, dense, mathworld, weisstein, eric, williams, louis, 1976, 14th, southeast, 101, 503561, 503582, modification, improvements, exploits, gain, advantages, setting, affect, guaranteed, inserting, alternating, pattern, maximizes, formal, minimal, quickly, outgrows, outperforms, 75n, showed, compared, solely, let, minimize, turns, proved, already, consecutive, equivalently, halves, interior, matter, div, anthony, lin, q81434400, 2470, 6345, 15347, wjs, 005, updated, reintegrated, reviewer, reports, submitted, calculation, multiplicative, equations, zero, partition_point, binary_search_by_key, binary_search_by, includes, without, having, cfarraybsearchvalues, core, usingcomparator, options, insortedrange, indexofobject, cocoa, objective, versions, generic, net, overloaded, slices, searchstrings, searchfloat64s, searchints, verb, phobos, default, offer, trisect, lowerbound, equalrange, assumesorted, sortedrange, equal_range, upper_bound, lower_bound, typically, official, include, routines, libraries, infinite, occur, correctly, exceeds, convey, exited, moved, place, who, incorrectly, defining, fixed, span, calculated, exceed, nonnegative, avoided, arithmetic, assigned, ninety, percent, provide, hours, working, mainly, answer, rare, study, shows, accurate, five, textbooks, remained, undetected, had, bug, nine, basic, comparatively, details, surprisingly, tricky, 1946, mention, seminal, foundational, presented, placed, reducing, chandra, introduced, stanford, equality, henry, moore, school, lectures, john, mauchly, items, allow, antiquity, earliest, inakibit, anu, babylon, dating, 500, entry, easier, letter, discovered, latin, finished, 1286, describe, rules, words, alphabetical, opposed, just, catholicon, aegean, islands, lexicographical, reciprocals, sexagesimal, 200, bce, proportion, providing, unordered, sqrt, natural, reliably, controls, reliability, yielded, variant, questions, ulam, game, entropy, upon, querying, incident, shortest, unequal, originally, various, elsewhere, routing, internet, protocol, mining, separately, reduces, storing, practice, compensates, estimated, distribution, estimates, basis, guess, needed, estimate, specify, estimating, starts, afterwards, sets, switches, before, started, becomes, improvement, lies, beginning, subsequent, containing, differences, computed, differ, amount, reduce, subtracts, calculate, decimal, advantage, properties, thus, consuming, lack, combination, approaches, mitigate, retaining, tries, fusion, van, emde, boas, suffer, false, positives, suited, simplest, limited, compactly, requiring, judy1, handles, implementing, maps, generally, ideal, them, supports, amortized, lend, hard, structured, generalizes, frequently, organize, term, databases, imperfectly, balance, rarely, produce, severely, imbalanced, approaching, principle, arranged, retain, allows, needs, unsorted, merge, quicksort, interleaved, retrieval, operation, complicate, especially, inserted, noted, 512, kib, tends, cause, how, requested, tend, causing, collisions, aliasing, fetch, meaning, handle, addresses, hitting, happens, setup, manage, areas, affected, prevented, offsetting, split, divides, thrashing, addressable, translation, lookaside, buffer, architectures, hardware, separate, processors, recently, sequentially, distant, probing, locality, contributor, leads, despite, dependent, nature, branches, conditional, moves, steel, bank, kind, differently, nan, total, analyzing, increases, double, achieved, significant, digital, checking, cuts, taken, guarantees, maximum, times, slight, compensate, determined, augmenting, fewer, remains, extended, equivalent, specified, connections, passes, through, corresponding, counting, represents, depends, word, exhibit, filled, completely, eliminate, dividing, ensures, subarrays, approximately, denotes, argument, cdot, analyzed, viewing, rest, fashion, starting, traversed, depending, adjusted, down, entries, those, whichever, closer, performs, trivial, extend, operates, seeking, adapted, shown, binary_search_rightmost, binary_search_leftmost, geq, consider, returns, sometimes, necessary, duplicated, exists, binary_search_alternative, neq, alternatively, appears, iterative, track, boundaries, variable, remain, refers, conveys, uses, subroutine, cdots, ldots, begins, particular, solves, fields, able, wider, relative, absent, again, repeating, empty, chop, yes, finite, continuous, redirected, free, encyclopedia, item, wikibooks, projects, printable, download, print, export, switch, legacy, parser, get, shortened, url, permanent, link, actions, talk, tiếng, việt, oʻzbekcha, ўзбекча, українська, türkçe, ไทย, தமிழ், svenska, српски, srpski, shqip, slovenščina, slovenčina, русский, română, português, polski, norsk, bokmål, nederlands, മലയാളം, македонски, 한국어, ಕನ್ನಡ, ქართული, 日本語, italiano, bahasa, indonesia, interlingua, हिन्दी, עברית, français, suomi, فارسی, eesti, español, ελληνικά, deutsch, čeština, català, বাংলা, български, azərbaycanca, الدارجة, العربية, top, personal, special, pages, recent, community, portal, learn, contribute, events, navigation,
Text of the page (random words):
ll but very large n textstyle n c 18 19 additional considerations edit cost of comparison edit in analyzing the performance of binary search another consideration is the time required to compare two elements for integers and strings the time required increases linearly as the encoding length usually the number of bits of the elements increase for example comparing a pair of 64 bit unsigned integers would require comparing up to double the bits as comparing a pair of 32 bit unsigned integers the worst case is achieved when the integers are equal this can be significant when the encoding lengths of the elements are large such as with large integer types or long strings which makes comparing elements expensive furthermore comparing floating point values the most common digital representation of real numbers is often more expensive than comparing integers or short strings fast floating point comparison is possible via comparing as an integer however this kind of comparison forms a total order which makes every floating point value compare differently from each other and the same as itself this is different from the typical comparison where 0 0 should be the same as 0 0 and nan should not compare the same as any other value including itself 20 21 branch prediction edit according to steel bank common lisp contributor paul khuong binary search leads to very few branch mispredictions despite its data dependent nature this is in part because most of it can be expressed as conditional moves instead of branches the same applies to most logarithmic divide and conquer search algorithms 22 cache usage edit on most computer architectures the processor has a hardware cache separate from ram since they are located within the processor itself caches are much faster to access but usually store much less data than ram therefore most processors store memory locations that have been accessed recently along with memory locations close to it for example when an array element is accessed the element itself may be stored along with the elements that are stored close to it in ram making it faster to sequentially access array elements that are close in index to each other locality of reference on a sorted array binary search can jump to distant memory locations if the array is large unlike algorithms such as linear search and linear probing in hash tables which access elements in sequence this adds slightly to the running time of binary search for large arrays on most systems 23 paul khuong has noted that binary search on large 512 kib arrays of exactly a power of two size tends to cause an additional problem with how cpu caches are implemented specifically the translation lookaside buffer tlb is often implemented as a content addressable memory cam with the key usually being the lower bits of a requested address when searching on an array of exactly a power of two size memory address with the same lower bits tend to be accessed causing collisions aliasing with the key used to fetch the cam the typical tlb is 4 way associative meaning it can handle at most four addresses hitting the same key after which tlb thrashing happens although the other levels of cpu caches also use a similar setup they manage smaller areas with a higher way count usually 8 or 16 so they are less affected this can be prevented by offsetting the split point of the binary search so it divides at 31 64 instead of exactly the middle 24 binary search versus other schemes edit sorted arrays with binary search are a very inefficient solution when insertion and deletion operations are interleaved with retrieval taking o n textstyle o n time for each such operation in addition sorted arrays can complicate memory use especially when elements are often inserted into the array 25 there are other data structures that support much more efficient insertion and deletion binary search can be used to perform exact matching and set membership determining whether a target value is in a collection of values there are data structures that support faster exact matching and set membership however unlike many other searching schemes binary search can be used for efficient approximate matching usually performing such matches in o log n textstyle o log n time regardless of the type or structure of the values themselves 26 in addition there are some operations like finding the smallest and largest element that can be performed efficiently on a sorted array 11 linear search edit linear search is a simple search algorithm that checks every record until it finds the target value linear search can be done on a linked list which allows for faster insertion and deletion than an array binary search is faster than linear search for sorted arrays except if the array is short although the array needs to be sorted beforehand d 28 all sorting algorithms based on comparing elements such as quicksort and merge sort require at least o n log n textstyle o n log n comparisons in the worst case 29 unlike linear search binary search can be used for efficient approximate matching there are operations such as finding the smallest and largest element that can be done efficiently on a sorted array but not on an unsorted array 30 trees edit binary search trees are searched using an algorithm similar to binary search a binary search tree is a binary tree data structure that works based on the principle of binary search the records of the tree are arranged in sorted order and each record in the tree can be searched using an algorithm similar to binary search taking on average logarithmic time insertion and deletion also require on average logarithmic time in binary search trees this can be faster than the linear time insertion and deletion of sorted arrays and binary trees retain the ability to perform all the operations possible on a sorted array including range and approximate queries 26 31 however binary search is usually more efficient for searching as binary search trees will most likely be imperfectly balanced resulting in slightly worse performance than binary search this even applies to balanced binary search trees binary search trees that balance their own nodes because they rarely produce the tree with the fewest possible levels except for balanced binary search trees the tree may be severely imbalanced with few internal nodes with two children resulting in the average and worst case search time approaching n textstyle n comparisons e binary search trees take more space than sorted arrays 33 binary search trees lend themselves to fast searching in external memory stored in hard disks as binary search trees can be efficiently structured in filesystems the b tree generalizes this method of tree organization b trees are frequently used to organize long term storage such as databases and filesystems 34 35 hashing edit for implementing associative arrays hash tables a data structure that maps keys to records using a hash function are generally faster than binary search on a sorted array of records 36 most hash table implementations require only amortized constant time on average f 38 however hashing is not useful for approximate matches such as computing the next smallest next largest and nearest key as the only information given on a failed search is that the target is not present in any record 39 binary search is ideal for such matches performing them in logarithmic time binary search also supports approximate matches some operations like finding the smallest and largest element can be done efficiently on sorted arrays but not on hash tables 26 set membership algorithms edit a related problem to search is set membership any algorithm that does lookup like binary search can also be used for set membership there are other algorithms that are more specifically suited for set membership a bit array is the simplest useful when the range of keys is limited it compactly stores a collection of bits with each bit representing a single key within the range of keys bit arrays are very fast requiring only o 1 textstyle o 1 time 40 the judy1 type of judy array handles 64 bit keys efficiently 41 for approximate results bloom filters another probabilistic data structure based on hashing store a set of keys by encoding the keys using a bit array and multiple hash functions bloom filters are much more space efficient than bit arrays in most cases and not much slower with k textstyle k hash functions membership queries require only o k textstyle o k time however bloom filters suffer from false positives g h 43 other data structures edit there exist data structures that may improve on binary search in some cases for both searching and other operations available for sorted arrays for example searches approximate matches and the operations available to sorted arrays can be performed more efficiently than binary search on specialized data structures such as van emde boas trees fusion trees tries and bit arrays these specialized data structures are usually only faster because they take advantage of the properties of keys with a certain attribute usually keys that are small integers and thus will be time or space consuming for keys that lack that attribute 26 as long as the keys can be ordered these operations can always be done at least efficiently on a sorted array regardless of the keys some structures such as judy arrays use a combination of approaches to mitigate this while retaining efficiency and the ability to perform approximate matching 41 variations edit uniform binary search edit main article uniform binary search uniform binary search stores the difference between the current and the two next possible middle elements instead of specific bounds uniform binary search stores instead of the lower and upper bounds the difference in the index of the middle element from the current iteration to the next iteration a lookup table containing the differences is computed beforehand for example if the array to be searched is 1 2 3 4 5 6 7 8 9 10 11 the middle element m displaystyle m would be 6 in this case the middle element of the left subarray 1 2 3 4 5 is 3 and the middle element of the right subarray 7 8 9 10 11 is 9 uniform binary search would store the value of 3 as both indices differ from 6 by this same amount 44 to reduce the search space the algorithm either adds or subtracts this change from the index of the middle element uniform binary search may be faster on systems where it is inefficient to calculate the midpoint such as on decimal computers 45 exponential search edit main article exponential search visualization of exponential searching finding the upper bound for the subsequent binary search exponential search extends binary search to unbounded lists it starts by finding the first element with an index that is both a power of two and greater than the target value afterwards it sets that index as the upper bound and switches to binary search a search takes log 2 x 1 textstyle lfloor log _ 2 x 1 rfloor iterations before binary search is started and at most log 2 x textstyle lfloor log _ 2 x rfloor iterations of the binary search where x textstyle x is the position of the target value exponential search works on bounded lists but becomes an improvement over binary search only if the target value lies near the beginning of the array 46 interpolation search edit main article interpolation search visualization of interpolation search using linear interpolation in this case no searching is needed because the estimate of the target s location within the array is correct other implementations may specify another function for estimating the target s location instead of calculating the midpoint interpolation search estimates the position of the target value taking into account the lowest and highest elements in the array as well as length of the array it works on the basis that the midpoint is not the best guess in many cases for example if the target value is close to the highest element in the array it is likely to be located near the end of the array 47 a common interpolation function is linear interpolation if a displaystyle a is the array l r displaystyle l r are the lower and upper bounds respectively and t displaystyle t is the target then the target is estimated to be about t a l a r a l displaystyle t a_ l a_ r a_ l of the way between l displaystyle l and r displaystyle r when linear interpolation is used and the distribution of the array elements is uniform or near uniform interpolation search makes o log log n textstyle o log log n comparisons 47 48 49 in practice interpolation search is slower than binary search for small arrays as interpolation search requires extra computation its time complexity grows more slowly than binary search but this only compensates for the extra computation for large arrays 47 fractional cascading edit main article fractional cascading in fractional cascading each array has pointers to every second element of another array so only one binary search has to be performed to search all the arrays fractional cascading is a technique that speeds up binary searches for the same element in multiple sorted arrays searching each array separately requires o k log n textstyle o k log n time where k textstyle k is the number of arrays fractional cascading reduces this to o k log n textstyle o k log n by storing specific information in each array about each element and its position in the other arrays 50 51 fractional cascading was originally developed to efficiently solve various computational geometry problems fractional cascading has been applied elsewhere such as in data mining and internet protocol routing 50 generalization to graphs edit binary search has been generalized to work on certain types of graphs where the target value is stored in a vertex instead of an array element binary search trees are one such generalization when a vertex node in the tree is queried the algorithm either learns that the vertex is the target or otherwise which subtree the target would be located in however this can be further generalized as follows given an undirected positively weighted graph and a target vertex the algorithm learns upon querying a vertex that it is equal to the target or it is given an incident edge that is on the shortest path from the queried vertex to the target the standard binary search algorithm is simply the case where the graph is a path similarly binary search trees are the case where the edges to the left or right subtrees are given when the queried vertex is unequal to the target for all undirected positively weighted graphs there is an algorithm that finds the target vertex in o log n displaystyle o log n queries in the worst case 52 noisy binary search edit in noisy binary search there is a certain probability that a comparison is incorrect noisy binary search algorithms solve the case where the algorithm cannot reliably compare elements of the array for each pair of elements there...
|
