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):
sor and nearest neighbor are shown for the target value 5 displaystyle 5 which is not in the array the above procedure only performs exact matches finding the position of a target value however it is trivial to extend binary search to perform approximate matches because binary search operates on sorted arrays for example binary search can be used to compute for a given value its rank the number of smaller elements predecessor next smallest element successor next largest element and nearest neighbor range queries seeking the number of elements between two values can be performed with two rank queries 11 rank queries can be performed with the procedure for finding the leftmost element the number of elements less than the target value is returned by the procedure 11 predecessor queries can be performed with rank queries if the rank of the target value is r displaystyle r its predecessor is r 1 displaystyle r 1 12 for successor queries the procedure for finding the rightmost element can be used if the result of running the procedure for the target value is r displaystyle r then the successor of the target value is r 1 displaystyle r 1 12 the nearest neighbor of the target value is either its predecessor or successor whichever is closer range queries are also straightforward 12 once the ranks of the two values are known the number of elements greater than or equal to the first value and less than the second is the difference of the two ranks this count can be adjusted up or down by one according to whether the endpoints of the range should be considered to be part of the range and whether the array contains entries matching those endpoints 13 performance edit a tree representing binary search the array being searched here is 20 30 40 50 80 90 100 displaystyle 20 30 40 50 80 90 100 and the target value is 40 displaystyle 40 the worst case is reached when the search reaches the deepest level of the tree while the best case is reached when the target value is the middle element in terms of the number of comparisons the performance of binary search can be analyzed by viewing the run of the procedure on a binary tree the root node of the tree is the middle element of the array the middle element of the lower half is the left child node of the root and the middle element of the upper half is the right child node of the root the rest of the tree is built in a similar fashion starting from the root node the left or right subtrees are traversed depending on whether the target value is less or more than the node under consideration 6 14 in the worst case binary search makes log 2 n 1 textstyle lfloor log _ 2 n 1 rfloor iterations of the comparison loop where the textstyle lfloor cdot rfloor notation denotes the floor function that yields the greatest integer less than or equal to the argument and log 2 textstyle log _ 2 is the binary logarithm this is because the worst case is reached when the search reaches the deepest level of the tree and there are always log 2 n 1 textstyle lfloor log _ 2 n 1 rfloor levels in the tree for any binary search the worst case may also be reached when the target element is not in the array if n textstyle n is one less than a power of two then this is always the case otherwise the search may perform log 2 n 1 textstyle lfloor log _ 2 n 1 rfloor iterations if the search reaches the deepest level of the tree however it may make log 2 n textstyle lfloor log _ 2 n rfloor iterations which is one less than the worst case if the search ends at the second deepest level of the tree 15 on average assuming that each element is equally likely to be searched binary search makes log 2 n 1 2 log 2 n 1 log 2 n 2 n displaystyle lfloor log _ 2 n rfloor 1 2 lfloor log _ 2 n rfloor 1 lfloor log _ 2 n rfloor 2 n iterations when the target element is in the array this is approximately equal to log 2 n 1 displaystyle log _ 2 n 1 iterations when the target element is not in the array binary search makes log 2 n 2 2 log 2 n 1 n 1 displaystyle lfloor log _ 2 n rfloor 2 2 lfloor log _ 2 n rfloor 1 n 1 iterations on average assuming that the range between and outside elements is equally likely to be searched 14 in the best case where the target value is the middle element of the array its position is returned after one iteration 16 in terms of iterations no search algorithm that works only by comparing elements can exhibit better average and worst case performance than binary search the comparison tree representing binary search has the fewest levels possible as every level above the lowest level of the tree is filled completely b otherwise the search algorithm can eliminate few elements in an iteration increasing the number of iterations required in the average and worst case this is the case for other search algorithms based on comparisons as while they may work faster on some target values the average performance over all elements is worse than binary search by dividing the array in half binary search ensures that the size of both subarrays are as similar as possible 14 space complexity edit binary search requires three pointers to elements which may be array indices or pointers to memory locations regardless of the size of the array therefore the space complexity of binary search is o 1 displaystyle o 1 in the word ram model of computation derivation of average case edit the average number of iterations performed by binary search depends on the probability of each element being searched the average case is different for successful searches and unsuccessful searches it will be assumed that each element is equally likely to be searched for successful searches for unsuccessful searches it will be assumed that the intervals between and outside elements are equally likely to be searched the average case for successful searches is the number of iterations required to search every element exactly once divided by n displaystyle n the number of elements the average case for unsuccessful searches is the number of iterations required to search an element within every interval exactly once divided by the n 1 displaystyle n 1 intervals 14 successful searches edit in the binary tree representation a successful search can be represented by a path from the root to the target node called an internal path the length of a path is the number of edges connections between nodes that the path passes through the number of iterations performed by a search given that the corresponding path has length l is l 1 displaystyle l 1 counting the initial iteration the internal path length is the sum of the lengths of all unique internal paths since there is only one path from the root to any single node each internal path represents a search for a specific element if there are n elements which is a positive integer and the internal path length is i n displaystyle i n then the average number of iterations for a successful search t n 1 i n n displaystyle t n 1 frac i n n with the one iteration added to count the initial iteration 14 since binary search is the optimal algorithm for searching with comparisons this problem is reduced to calculating the minimum internal path length of all binary trees with n nodes which is equal to 17 i n k 1 n log 2 k displaystyle i n sum _ k 1 n left lfloor log _ 2 k right rfloor for example in a 7 element array the root requires one iteration the two elements below the root require two iterations and the four elements below require three iterations in this case the internal path length is 17 k 1 7 log 2 k 0 2 1 4 2 2 8 10 displaystyle sum _ k 1 7 left lfloor log _ 2 k right rfloor 0 2 1 4 2 2 8 10 the average number of iterations would be 1 10 7 2 3 7 displaystyle 1 frac 10 7 2 frac 3 7 based on the equation for the average case the sum for i n displaystyle i n can be simplified to 14 i n k 1 n log 2 k n 1 log 2 n 1 2 log 2 n 1 1 2 displaystyle i n sum _ k 1 n left lfloor log _ 2 k right rfloor n 1 left lfloor log _ 2 n 1 right rfloor 2 left lfloor log _ 2 n 1 right rfloor 1 2 substituting the equation for i n displaystyle i n into the equation for t n displaystyle t n 14 t n 1 n 1 log 2 n 1 2 log 2 n 1 1 2 n log 2 n 1 2 log 2 n 1 log 2 n 2 n displaystyle t n 1 frac n 1 left lfloor log _ 2 n 1 right rfloor 2 left lfloor log _ 2 n 1 right rfloor 1 2 n lfloor log _ 2 n rfloor 1 2 lfloor log _ 2 n rfloor 1 lfloor log _ 2 n rfloor 2 n for integer n this is equivalent to the equation for the average case on a successful search specified above unsuccessful searches edit unsuccessful searches can be represented by augmenting the tree with external nodes which forms an extended binary tree if an internal node or a node present in the tree has fewer than two child nodes then additional child nodes called external nodes are added so that each internal node has two children by doing so an unsuccessful search can be represented as a path to an external node whose parent is the single element that remains during the last iteration an external path is a path from the root to an external node the external path length is the sum of the lengths of all unique external paths if there are n displaystyle n elements which is a positive integer and the external path length is e n displaystyle e n then the average number of iterations for an unsuccessful search is t n e n n 1 displaystyle t n frac e n n 1 with the one iteration added to count the initial iteration the external path length is divided by n 1 displaystyle n 1 instead of n displaystyle n because there are n 1 displaystyle n 1 external paths representing the intervals between and outside the elements of the array 14 this problem can similarly be reduced to determining the minimum external path length of all binary trees with n displaystyle n nodes for all binary trees the external path length is equal to the internal path length plus 2 n displaystyle 2n 17 substituting the equation for i n displaystyle i n 14 e n i n 2 n n 1 log 2 n 1 2 log 2 n 1 1 2 2 n n 1 log 2 n 2 2 log 2 n 1 displaystyle e n i n 2n left n 1 left lfloor log _ 2 n 1 right rfloor 2 left lfloor log _ 2 n 1 right rfloor 1 2 right 2n n 1 lfloor log _ 2 n rfloor 2 2 lfloor log _ 2 n rfloor 1 substituting the equation for e n displaystyle e n into the equation for t n displaystyle t n the average case for unsuccessful searches can be determined 14 t n n 1 log 2 n 2 2 log 2 n 1 n 1 log 2 n 2 2 log 2 n 1 n 1 displaystyle t n frac n 1 lfloor log _ 2 n rfloor 2 2 lfloor log _ 2 n rfloor 1 n 1 lfloor log _ 2 n rfloor 2 2 lfloor log _ 2 n rfloor 1 n 1 performance of alternative procedure edit each iteration of the binary search procedure defined above makes one or two comparisons checking if the middle element is equal to the target in each iteration assuming that each element is equally likely to be searched each iteration makes 1 5 comparisons on average a variation of the algorithm checks whether the middle element is equal to the target at the end of the search on average this eliminates half a comparison from each iteration this slightly cuts the time taken per iteration on most computers however it guarantees that the search takes the maximum number of iterations on average adding one iteration to the search because the comparison loop is performed only log 2 n 1 textstyle lfloor log _ 2 n 1 rfloor times in the worst case the slight increase in efficiency per iteration does not compensate for the extra iteration for all 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 deletio...
|
