{"id":918,"date":"2020-04-02T21:38:53","date_gmt":"2020-04-03T04:38:53","guid":{"rendered":"http:\/\/209.126.2.187\/?p=918"},"modified":"2020-04-03T17:59:44","modified_gmt":"2020-04-04T00:59:44","slug":"binary-search-the-result","status":"publish","type":"post","link":"https:\/\/nanzhou.cc\/index.php\/2020\/04\/02\/binary-search-the-result\/","title":{"rendered":"Binary Search the Result"},"content":{"rendered":"\n

Summary <\/h2>\n\n\n\n

In this post, I will introduce some problems which could binary search the best result.<\/p>\n\n\n\n

The problems in this category usually ask for a best value. The value could fall into the range of [min, max]<\/code>. Another important property is that if the value at the middle is not achievable, we could eliminate a half the range. <\/p>\n\n\n\n

A possible solution is that we binary search this best value, and check if it is achievable or not. Repeat until we get a single answer. <\/p>\n\n\n\n

OJ<\/h2>\n\n\n\n\n\n\n\n\t\n\n\t\n\t
<\/td>Trick<\/th>Difficulty<\/th>\n<\/tr>\n<\/thead>\n
LC 644 Maximum Average Subarray II<\/a><\/td>Binary Search Result + Greedy + Maximum Subarray Sum<\/td>6 points<\/td>\n<\/tr>\n
LC 410 Split Array Largest Sum<\/a><\/td>Binary Search Result + Greedy<\/td>6-7 points<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n\n\n\n\n

Details<\/h2>\n\n\n\n

LC 410<\/a> Split Array Largest Sum<\/h4>\n\n\n\n

Given an array which consists of non-negative integers and an integer\u00a0m<\/em>, you can split the array into\u00a0m<\/em>\u00a0non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these\u00a0m<\/em>\u00a0subarrays.<\/p>\n\n\n\n

The DP solution is not difficult.<\/p>\n\n\n\n

\/\/ alg[n][M] = 0\nalg[i][m] = \n   min{max(alg[j + 1][m - 1], sum[i, ..., j]), for j in [i, ..., n - 1]}<\/code><\/pre>\n\n\n\n
The problem could be solved via binary searching the result. <\/p>\n\n\n\n
  1. The minimum value possible is min_element(nums)<\/code>; the maximum value possible is sum(nums)<\/code><\/li>
  2. If a value mid<\/code> is not possible, it is not possible for values smaller than mid;  <\/li>
  3. check<\/code> could be done in O(n)<\/code> by greedily dividing groups: from left to right, as long as current sum is smaller than mid<\/code>, insert it into the current group. If finally count <= K<\/code>, we know mid<\/code> is possible, since we could further divide some groups but not increase the largest sum. The tricky part is if count > K<\/code>, we know all smaller values are not possible. This could be proved by contradiction. If a smaller value is possible, the first subarray would be smaller, so is the second array, which causes the number of subarrays will be not smaller than count<\/code>, which causes the contradiction. <\/li><\/ol>\n","protected":false},"excerpt":{"rendered":"
    Summary In this post, I will introduce some problems which could binary search the best result. The problems in this category usually ask for a best value. The value could fall into the range of [min, max]. Another important property is that if the value at the middle is not achievable, we could eliminate a…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48,57],"tags":[],"class_list":["post-918","post","type-post","status-publish","format-standard","hentry","category-alg","category-binary-search"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/918","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/comments?post=918"}],"version-history":[{"count":7,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/918\/revisions"}],"predecessor-version":[{"id":928,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/918\/revisions\/928"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=918"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=918"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=918"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}