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):
orted functions with methods contains equalrange lowerbound and trisect that use binary search techniques by default for ranges that offer random access 73 cobol provides the search all verb for performing binary searches on cobol ordered tables 74 go s sort standard library package contains the functions search searchints searchfloat64s and searchstrings which implement general binary search as well as specific implementations for searching slices of integers floating point numbers and strings respectively 75 java offers a set of overloaded binarysearch static methods in the classes arrays and collections in the standard java util package for performing binary searches on java arrays and on list s respectively 76 77 microsoft s net framework 2 0 offers static generic versions of the binary search algorithm in its collection base classes an example would be system array s method binarysearch t t array t value 78 for objective c the cocoa framework provides the nsarray indexofobject insortedrange options usingcomparator method in mac os x 10 6 79 apple s core foundation c framework also contains a cfarraybsearchvalues function 80 python provides the bisect module that keeps a list in sorted order without having to sort the list after each insertion 81 ruby s array class includes a bsearch method with built in approximate matching 82 rust s slice primitive provides binary_search binary_search_by binary_search_by_key and partition_point 83 see also edit bisection method algorithm for finding a zero of a function the same idea used to solve equations in the real numbers multiplicative binary search binary search variation with simplified midpoint calculation notes and references edit this article was submitted to wikijournal of science for external academic peer review in 2018 reviewer reports the updated content was reintegrated into the wikipedia page under a cc by sa 3 0 license 2019 the version of record as reviewed is anthony lin et al 2 july 2019 binary search algorithm pdf wikijournal of science 2 1 5 doi 10 15347 wjs 2019 005 issn 2470 6345 wikidata q81434400 notes edit the o displaystyle o is big o notation and log displaystyle log is the logarithm in big o notation the base of the logarithm does not matter since every logarithm of a given base is a constant factor of another logarithm of another base that is log b n log k n log k b displaystyle log _ b n log _ k n div log _ k b where log k b displaystyle log _ k b is a constant any search algorithm based solely on comparisons can be represented using a binary comparison tree an internal path is any path from the root to an existing node let i displaystyle i be the internal path length the sum of the lengths of all internal paths if each element is equally likely to be searched the average case is 1 i n displaystyle 1 frac i n or simply one plus the average of all the internal path lengths of the tree this is because internal paths represent the elements that the search algorithm compares to the target the lengths of these internal paths represent the number of iterations after the root node adding the average of these lengths to the one iteration at the root yields the average case therefore to minimize the average number of comparisons the internal path length i displaystyle i must be minimized it turns out that the tree for binary search minimizes the internal path length knuth 1998 proved that the external path length the path length over all nodes where both children are present for each already existing node is minimized when the external nodes the nodes with no children lie within two consecutive levels of the tree this also applies to internal paths as internal path length i displaystyle i is linearly related to external path length e displaystyle e for any tree of n displaystyle n nodes i e 2 n displaystyle i e 2n when each subtree has a similar number of nodes or equivalently the array is divided into halves in each iteration the external nodes as well as their interior parent nodes lie within two levels it follows that binary search minimizes the number of average comparisons as its comparison tree has the lowest possible internal path length 14 knuth 1998 showed on his mix computer model which knuth designed as a representation of an ordinary computer that the average running time of this variation for a successful search is 17 5 log 2 n 17 textstyle 17 5 log _ 2 n 17 units of time compared to 18 log 2 n 16 textstyle 18 log _ 2 n 16 units for regular binary search the time complexity for this variation grows slightly more slowly but at the cost of higher initial complexity 18 knuth 1998 performed a formal time performance analysis of both of these search algorithms on knuth s mix computer which knuth designed as a representation of an ordinary computer binary search takes on average 18 log n 16 textstyle 18 log n 16 units of time for a successful search while linear search with a sentinel node at the end of the list takes 1 75 n 8 5 n mod 2 4 n textstyle 1 75n 8 5 frac n text mod 2 4n units linear search has lower initial complexity because it requires minimal computation but it quickly outgrows binary search in complexity on the mix computer binary search only outperforms linear search with a sentinel if n 44 textstyle n 44 14 27 inserting the values in sorted order or in an alternating lowest highest key pattern will result in a binary search tree that maximizes the average and worst case search time 32 it is possible to search some hash table implementations in guaranteed constant time 37 this is because simply setting all of the bits which the hash functions point to for a specific key can affect queries for other keys which have a common hash location for one or more of the functions 42 there exist improvements of the bloom filter which improve on its complexity or support deletion for example the cuckoo filter exploits cuckoo hashing to gain these advantages 42 that is arrays of length 1 3 7 15 31 62 citations edit williams jr louis f 22 april 1976 a modification to the half interval search binary search method proceedings of the 14th acm southeast conference acm pp 95 101 doi 10 1145 503561 503582 archived from the original on 12 march 2017 retrieved 29 june 2018 1 2 knuth 1998 6 2 1 searching an ordered table subsection binary search butterfield ngondi 2016 p 46 cormen et al 2009 p 39 weisstein eric w binary search mathworld 1 2 flores ivan madpis george 1 september 1971 average binary search length for dense ordered lists communications of the acm 14 9 602 603 doi 10 1145 362663 362752 issn 0001 0782 s2cid 43325465 1 2 3 knuth 1998 6 2 1 searching an ordered table subsection algorithm b 1 2 3 4 bottenbruch hermann 1 april 1962 structure and use of algol 60 journal of the acm 9 2 161 221 doi 10 1145 321119 321120 issn 0004 5411 s2cid 13406983 procedure is described at p 214 43 titled program for binary search 1 2 3 4 5 6 knuth 1998 6 2 1 searching an ordered table subsection history and bibliography 1 2 kasahara morishita 2006 pp 8 9 1 2 3 sedgewick wayne 2011 3 1 subsection rank and selection 1 2 3 goldman goldman 2008 pp 461 463 sedgewick wayne 2011 3 1 subsection range queries 1 2 3 4 5 6 7 8 9 10 11 12 knuth 1998 6 2 1 searching an ordered table subsection further analysis of binary search knuth 1998 6 2 1 searching an ordered table theorem b chang 2003 p 169 1 2 3 knuth 1997 2 3 4 5 path length 1 2 knuth 1998 6 2 1 searching an ordered table subsection exercise 23 rolfe timothy j 1997 analytic derivation of comparisons in binary search acm signum newsletter 32 4 15 19 doi 10 1145 289251 289255 s2cid 23752485 herf michael december 2001 radix tricks stereopsis graphics implement total_cmp for f32 f64 by golddranks pull request 72568 rust lang rust github contains relevant quotations from ieee 754 2008 and 2019 contains a type pun implementation and explanation binary search eliminates branch mispredictions paul khuong some lisp pvk ca khuong paul virak morin pat 2017 array layouts for comparison based searching journal of experimental algorithmics 22 article 1 3 arxiv 1509 05053 doi 10 1145 3053370 s2cid 23752485 binary search is a pathological case for caches paul khuong some lisp pvk ca knuth 1997 2 2 2 sequential allocation 1 2 3 4 beame paul fich faith e 2001 optimal bounds for the predecessor problem and related problems journal of computer and system sciences 65 1 38 72 doi 10 1006 jcss 2002 1822 knuth 1998 answers to exercises 6 2 1 for exercise 5 knuth 1998 6 2 1 searching an ordered table knuth 1998 5 3 1 minimum comparison sorting sedgewick wayne 2011 3 2 ordered symbol tables sedgewick wayne 2011 3 2 binary search trees subsection order based methods and deletion knuth 1998 6 2 2 binary tree searching subsection but what about the worst case sedgewick wayne 2011 3 5 applications which symbol table implementation should i use knuth 1998 5 4 9 disks and drums knuth 1998 6 2 4 multiway trees knuth 1998 6 4 hashing knuth 1998 6 4 hashing subsection history dietzfelbinger martin karlin anna mehlhorn kurt meyer auf der heide friedhelm rohnert hans tarjan robert e august 1994 dynamic perfect hashing upper and lower bounds siam journal on computing 23 4 738 761 doi 10 1137 s0097539791194094 morin pat hash tables pdf p 1 archived pdf from the original on 9 october 2022 retrieved 28 march 2016 knuth 2011 7 1 3 bitwise tricks and techniques 1 2 silverstein alan judy iv shop manual pdf hewlett packard pp 80 81 archived pdf from the original on 9 october 2022 1 2 fan bin andersen dave g kaminsky michael mitzenmacher michael d 2014 cuckoo filter practically better than bloom proceedings of the 10th acm international on conference on emerging networking experiments and technologies pp 75 88 doi 10 1145 2674005 2674994 bloom burton h 1970 space time trade offs in hash coding with allowable errors communications of the acm 13 7 422 426 doi 10 1145 362686 362692 s2cid 7931252 knuth 1998 6 2 1 searching an ordered table subsection an important variation knuth 1998 6 2 1 searching an ordered table subsection algorithm u moffat turpin 2002 p 33 1 2 3 knuth 1998 6 2 1 searching an ordered table subsection interpolation search knuth 1998 6 2 1 searching an ordered table subsection exercise 22 perl yehoshua itai alon avni haim 1978 interpolation search a log log n search communications of the acm 21 7 550 553 doi 10 1145 359545 359557 s2cid 11089655 1 2 3 chazelle bernard liu ding 6 july 2001 lower bounds for intersection searching and fractional cascading in higher dimension 33rd acm symposium on theory of computing acm pp 322 329 doi 10 1145 380752 380818 isbn 978 1 58113 349 3 retrieved 30 june 2018 chazelle bernard liu ding 1 march 2004 lower bounds for intersection searching and fractional cascading in higher dimension pdf journal of computer and system sciences 68 2 269 284 doi 10 1016 j jcss 2003 07 003 issn 0022 0000 archived pdf from the original on 9 october 2022 retrieved 30 june 2018 emamjomeh zadeh ehsan kempe david singhal vikrant 2016 deterministic and probabilistic binary search in graphs 48th acm symposium on theory of computing pp 519 532 arxiv 1503 00805 doi 10 1145 2897518 2897656 ben or michael hassidim avinatan 2008 the bayesian learner is optimal for noisy binary search and pretty good for quantum as well pdf 49th symposium on foundations of computer science pp 221 230 doi 10 1109 focs 2008 58 isbn 978 0 7695 3436 7 archived pdf from the original on 9 october 2022 pelc andrzej 1989 searching with known error probability theoretical computer science 63 2 185 202 doi 10 1016 0304 3975 89 90077 7 rivest ronald l meyer albert r kleitman daniel j winklmann k coping with errors in binary search procedures 10th acm symposium on theory of computing doi 10 1145 800133 804351 pelc andrzej 2002 searching games with errors fifty years of coping with liars theoretical computer science 270 1 2 71 109 doi 10 1016 s0304 3975 01 00303 6 rényi alfréd 1961 on a problem in information theory magyar tudományos akadémia matematikai kutató intézetének közleményei 6 515 516 mr 0143666 høyer peter neerbek jan shi yaoyun 2002 quantum complexities of ordered searching sorting and element distinctness algorithmica 34 4 429 448 arxiv quant ph 0102078 doi 10 1007 s00453 002 0976 3 s2cid 13717616 childs andrew m landahl andrew j parrilo pablo a 2007 quantum algorithms for the ordered search problem via semidefinite programming physical review a 75 3 032335 arxiv quant ph 0608161 bibcode 2007phrva 75c2335c doi 10 1103 physreva 75 032335 s2cid 41539957 grover lov k 1996 a fast quantum mechanical algorithm for database search 28th acm symposium on theory of computing philadelphia pa pp 212 219 arxiv quant ph 9605043 doi 10 1145 237814 237866 peterson william wesley 1957 addressing for random access storage ibm journal of research and development 1 2 130 146 doi 10 1147 rd 12 0130 2 n 1 oeis a000225 archived 8 june 2016 at the wayback machine retrieved 7 may 2016 lehmer derrick 1960 teaching combinatorial tricks to a computer combinatorial analysis proceedings of symposia in applied mathematics vol 10 pp 180 181 doi 10 1090 psapm 010 0113289 isbn 9780821813102 mr 0113289 cite book isbn date incompatibility help chazelle bernard guibas leonidas j 1986 fractional cascading i a data structuring technique pdf algorithmica 1 1 4 133 162 doi 10 1007 bf01840440 s2cid 12745042 chazelle bernard guibas leonidas j 1986 fractional cascading ii applications pdf algorithmica 1 1 4 163 191 doi 10 1007 bf01840441 s2cid 11232235 bentley 2000 4 1 the challenge of binary search pattis richard e 1988 textbook errors in binary searching sigcse bulletin 20 190 194 doi 10 1145 52965 53012 bloch joshua 2 june 2006 extra extra read all about it nearly all binary searches and mergesorts are broken google research blog archived from the original on 1 april 2016 retrieved 21 april 2016 ruggieri salvatore 2003 on computing the semi sum of two integers pdf information processing letters 87 2 67 71 doi 10 1016 s0020 0190 03 00263 1 archived pdf from the original on 3 july 2006 retrieved 19 march 2016 bentley 2000 4 4 principles bsearch binary search a sorted table the open group base specifications 7th ed the open group 2013 archived from the original on 21 march 2016 retrieved 28 march 2016 stroustrup 2013 p 945 std range d programming language dlang org retrieved 29 april 2020 unisys 2012 cobol ansi 85 programming reference manual vol 1 pp 598 601 package sort the go programming language archived from the original on 25 april 2016 retrieved 28 april 2016 java util arrays java platform standard edition 8 documentation oracle corporation archived from the original on 29 april 2016 retrieved 1 may 2016 java util collections java platform standard edition 8 documentation oracle corporation archived from the original on 23 april 2016 retrieved 1 may 2016 list t binarysearch method t microsoft developer network archived from the original on 7 may 2016 retrieved 10 april 2016 nsarray mac devel...
|
