{"id":109929,"date":"2024-06-24T07:00:00","date_gmt":"2024-06-24T14:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=109929"},"modified":"2024-06-24T07:50:24","modified_gmt":"2024-06-24T14:50:24","slug":"20240624-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20240624-00\/?p=109929","title":{"rendered":"Finding a specific value in a sequence of integers that changes by at most 1"},"content":{"rendered":"<p>Consider a sequence of integers with the property that the distance between consecutive values is at most 1. The puzzle is to find a sublinear algorithm for locating a given value, with the condition that the value you&#8217;re looking for is between the first and last values of the sequence (inclusive).<\/p>\n<p>In formulas,<\/p>\n<ul>\n<li><var>x<\/var>\u2080, \u2026, <var>x<\/var>\u2099 is a finite integer sequence.<\/li>\n<li>|<var>x<\/var>\u2096 \u2212 <var>x<\/var>\u2096\u208a\u2081| \u2264 1.<\/li>\n<li>The target integer value <var>v<\/var> satisfies the property that (<var>x<\/var>\u2099 \u2212 <var>v<\/var>)(<var>v<\/var> \u2212 <var>x<\/var>\u2080) \u2265 0.<\/li>\n<\/ul>\n<p>When I saw this puzzle, I thought, &#8220;Well, that&#8217;s obvious.&#8221;<\/p>\n<p>Look at it this way: Suppose each <var>x<\/var>\u209c represents an object&#8217;s location at time <var>t<\/var> = <var>k<\/var>. The requirement that |<var>x<\/var>\u2096 \u2212 <var>x<\/var>\u2096\u208a\u2081| \u2264 1 means that at each tick, the object can either move left one step (\u22121), move right one step (+1), or not move at all (0). Since the object can move only in steps, you know that it must eventually reach every integral point between its starting and ending point. (Otherwise, how did it reach its ending point?);<\/p>\n<p>You can think of this as the discrete version of the intermediate value theorem.<\/p>\n<p>Once viewed as a path problem, the solution is clearly to use a binary search. At each step, probe the midpoint <var>x<\/var>\u2098 of the range: If it equal to the target value <var>v<\/var>, then you&#8217;re done. If it is on the same side of <var>v<\/var> as <var>x<\/var>\u2080, then reduce the interval to <var>x<\/var>\u2098\u208a\u2081, \u2026, <var>x<\/var>\u2099. If it is on the same side as <var>x<\/var>\u2099, then reduce the interval to <var>x<\/var>\u2080, \u2026, <var>x<\/var>\u2098\u208b\u2081. Repeat on the reduced range until you find a hit.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>It&#8217;s basically a discrete version of the intermediate value theorem.<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-109929","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"<p>It&#8217;s basically a discrete version of the intermediate value theorem.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/109929","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=109929"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/109929\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=109929"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=109929"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=109929"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}