{"entities":{"Q1062762":{"pageid":1073514,"ns":120,"title":"Item:Q1062762","lastrevid":66062349,"modified":"2026-04-12T07:16:53Z","type":"item","id":"Q1062762","labels":{"en":{"language":"en","value":"Interpolation-binary search"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3915638"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062762$72F20D03-878F-4890-BA6C-3255A5580BD8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4cb03a76555728a7180cb8b2a1569a449a7d4e40","datavalue":{"value":{"text":"Interpolation-binary search","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1062762$53F8A713-B71C-4C35-878E-0333AE4959E7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"df834df0d7dfb8c410e5092c8b0d3167e01ef11c","datavalue":{"value":"0573.68031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062762$C4F85CB1-26A1-46C0-9DE5-D960796187A5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"45d261f0f504ea343ef2c41a2d5a5923e422b7a7","datavalue":{"value":"10.1016/0020-0190(85)90046-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062762$B7D6B934-A143-4351-9EC1-462E6EAE51EE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"db6df3606e104c2161180e2597803fd70c72d072","datavalue":{"value":{"entity-type":"item","numeric-id":557817,"id":"Q557817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062762$D10D2F76-515E-41AF-ABDE-9CDF653547F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6b9282b10997c72ed1a0822dc56ebc25b5c980cf","datavalue":{"value":{"entity-type":"item","numeric-id":853748,"id":"Q853748"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062762$822B415B-D1A2-4406-AB83-6171AD4ECC6F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062762$C09270AC-907A-4D1C-B86F-9213B22D64A0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1062762$C98BC808-07CA-4638-9E1C-7D5B3D4CF943","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f54c4c6edca4452a03aa091b53163543f50138e9","datavalue":{"value":"Consider an array of n records stored so that the keys are arranged in increasing order. Using binary search, the search for a record can be performed in time O(log n), both in the average and in the worst case. If the keys are uniformly distributed, an improved expected performance can be obtained by interpolation or, for \\(n<500\\), by interpolation-sequential search. Namely, the search can be performed in expected time O(log log n) by interpolation search, and \\((n\\pi /32)^{1/2}+O(1)\\) by interpolation- sequential search. Unfortunately, both techniques require O(n) time in the worst case.    In this paper it is shown that it is possible to search in O(log n) time in the worst case and, if the keys are uniformly distributed, in O(log log n) time in the average. This result is achieved by interpolation- binary search, a new technique which combines 'interpolation' and 'binary' steps; thus, the proposed algorithm represents an improvement on the existing methods.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062762$CA44A32C-9BC5-4F69-981A-5D51AC77D555","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062762$2DAEA07A-9888-45A3-9C4E-F174561E984F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062762$D1A24270-DB97-4CF8-8F2E-714426AA0D01","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9d872372ff415837a921772fcbe9a0800e708f55","datavalue":{"value":"3915638","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062762$4C4D0755-E2A6-41B8-BDC6-1AACB94F7E6B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fcebece2bd5624b0a52d8205295ea8a979bc0ab6","datavalue":{"value":"ordered array","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062762$5A9DD54C-40C5-4FF6-BF1E-9B06AAA49E0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e0c7481e3c5c308fc47ea6e648bd33e7ea295f7","datavalue":{"value":"searching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062762$8713072D-2F52-4DC6-90B8-B9EEA4A9E065","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f1233fcb0dab421cadc556062a0158877f404bd","datavalue":{"value":"multiple complexity objective","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062762$9F1120EF-A260-499F-92B9-ACFFEF68D624","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062762$03AA6FF4-2DBB-4366-882C-1E65FDF5CCCD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fa42abdd28f2a6544b2fd44bb3e3009e882c815e","datavalue":{"value":"https://doi.org/10.1016/0020-0190(85)90046-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1062762$3DB5CBA0-6C2D-461D-9A1C-9FFBED8A7FE5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8b47e2188b37b634440c097b9ffb6e442bc2d4eb","datavalue":{"value":"W1968801254","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062762$C7442110-74BB-455B-B33E-F6D70EF5229D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"50190214303031c003c378f4c83ccaba152648fc","datavalue":{"value":{"entity-type":"item","numeric-id":1241286,"id":"Q1241286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062762$418E93CF-36D5-4C04-BE92-18343A82398C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e0aafe4c2a93c70d54cd35396484215be92862e","datavalue":{"value":{"entity-type":"item","numeric-id":1257344,"id":"Q1257344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062762$B9F5A408-FE0B-4424-B44A-13EFEFD356D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"666ba8367cc7645a1d0022e864975b17180aeaf1","datavalue":{"value":{"entity-type":"item","numeric-id":1245570,"id":"Q1245570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062762$85316700-7AB9-4B75-B13C-5EBD807FAAA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1570cedada623a9706352d869c0e98026959282","datavalue":{"value":{"entity-type":"item","numeric-id":4157947,"id":"Q4157947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062762$42C5443C-6C10-4D21-A0A5-31076DD4A0D9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eace776803dd86a1b197c610dda5d76fd27a2e45","datavalue":{"value":{"entity-type":"item","numeric-id":3796766,"id":"Q3796766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"97dfe6c1642ad1cfc815b2c205e08e08f9a5994b","datavalue":{"value":{"amount":"+0.8726375102996826","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1062762$A8151FC6-9DAE-4AD4-866F-B03E0237850D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92be80599f3452b345fd168bb52b9fb3f2c7f6b7","datavalue":{"value":{"entity-type":"item","numeric-id":4630245,"id":"Q4630245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"556b0c72ca47075f3a729b600279b4b852b57fed","datavalue":{"value":{"amount":"+0.8598227500915527","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1062762$013E2611-A282-4BD2-A0F5-63A6AB491325","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d87b17ca4fbe43190e3d5975fe2b4ea624813c2","datavalue":{"value":{"entity-type":"item","numeric-id":3686050,"id":"Q3686050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0910715ee06f70ad81701aa6d6185744f8e798d","datavalue":{"value":{"amount":"+0.8319534063339233","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1062762$2C035712-8CB4-46EC-B2E7-210CA11BF194","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f702efbdb04e25687d8518bd3e8d821e2f9082ca","datavalue":{"value":{"entity-type":"item","numeric-id":1825662,"id":"Q1825662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"31c116d5c40b4b4d450f08714c349ab1e05a05f2","datavalue":{"value":{"amount":"+0.8300905227661133","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1062762$09A9DC9E-C499-4BCA-BF20-91E23D28D907","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ac0bce8e587902ac7b312aa1318847a016b8c8d3","datavalue":{"value":{"entity-type":"item","numeric-id":3140019,"id":"Q3140019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a768ba1465fcde2893aa29a5b26015dca603fdeb","datavalue":{"value":{"amount":"+0.8244056701660156","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1062762$A4001C48-CB5B-46D0-A119-457CEE8384FB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Interpolation-binary search","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Interpolation-binary_search"}}}}}