二分法(binary search)系列

35. Search Insert Position

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with <code>O(log n)</code> runtime complexity.

Example 1:

Example 2:

Example 3:

Example 4:

Example 5:

Constraints:

<code>nums</code> contains distinct values sorted in ascending order.

解法一：這種解法可以用于處理一些簡單的二分法問題

解法二：

l 和 r 所定義的出的數組範圍為 [l, r)，是左閉右開的也就是在後續的循環中， r 所指向的位置是不被包括在循環以内的， r 所代表的位置實際上是要查找的數組的最後一個元素的後一個元素。

因為是左閉右開的 r 初值為 nums.size() ，因為數組的最後一個元素的索引為 nums[nums.length - 1], 根據 r 定義最後一個元素的後一個元素即為 r = nums.length;

因為是左閉右開的循環結束條件的判斷中為 while(l < r) 因為對于左閉右開的區間 [2, 2) 這種數值是無意義的，是以當 r = l 的時候，就該結束循環了，是以隻有在 l < r 才繼續循環

因為是左閉右開的 r 的移動規則為 r = mid ，因為目前循環查找的為索引為 mid 位置的元素(即：（nums[mid] == target）)，下一次應該将查找範圍的右邊界設定為 mid 位置的前一個元素（[l, m - 1]），因為 r 指向最後一個元素的後一個元素，當 r = m ，下次的查找範圍就為 [l, r)即 [l, m - 1]

解法三：

正常寫法 1 中 l 和 r 的定義的範圍為 [l, r]，是左閉右閉的也就是在後續的循環中， r 所指向的位置是被包括在循環以内的， r 所代表的位置實際上是要查找的數組的最後一個元素。

因為是左閉右閉的 r 初值應為 nums.length - 1 ，因為數組的最後一個元素的索引為 nums[nums.length - 1], 根據 r 定義最後一個元素即為 r = nums.length - 1;

因為是左閉右閉循環結束條件的判斷中為 while(l < r) ，因為對于左閉右閉的區間 [2, 2] 這種數值是有意義的（包含元素 2），是以當 r = l 的時候，還有一個元素應該去查找，是以 l <= r 繼續循環

因為是左閉右閉 r 的移動規則為 r = mid - 1 ，因為目前循環被查找的為索引為 m 位置的元素(即：（nums[mid] == target）) ，下一次應該将查找範圍的右邊界設定為 m 位置的前一個元素（[l, mid - 1]），因為 r 指向最後一個元素 , 是以讓 r = mid - 1 ，下次的查找範就為 [l, r - 1] 即 [l, mid - 1]

33. Search in Rotated Sorted Array

There is an integer array <code>nums</code> sorted in ascending order (with distinct values).

Prior to being passed to your function, <code>nums</code> is possibly rotated at an unknown pivot index <code>k</code> (<code>1 <= k < nums.length</code>) such that the resulting array is <code>[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]</code> (0-indexed). For example, <code>[0,1,2,4,5,6,7]</code> might be rotated at pivot index <code>3</code> and become <code>[4,5,6,7,0,1,2]</code>.

Given the array <code>nums</code> after the possible rotation and an integer <code>target</code>, return the index of <code>target</code> if it is in <code>nums</code>, or <code>-1</code> if it is not in <code>nums</code>.

You must write an algorithm with <code>O(log n)</code> runtime complexity.

All values of <code>nums</code> are unique.

<code>nums</code> is an ascending array that is possibly rotated.

解法一: 二分法找到rotate的那個點（最小值位置），再用一個二分法搜尋target對應的半部分

解法二：遞歸二分解決

圖一

圖二

解法三：解法二的while loop 版本

81. Search in Rotated Sorted Array II

There is an integer array <code>nums</code> sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, <code>nums</code> is rotated at an unknown pivot index <code>k</code> (<code>0 <= k < nums.length</code>) such that the resulting array is <code>[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]</code> (0-indexed). For example, <code>[0,1,2,4,4,4,5,6,6,7]</code> might be rotated at pivot index <code>5</code> and become <code>[4,5,6,6,7,0,1,2,4,4]</code>.

Given the array <code>nums</code> after the rotation and an integer <code>target</code>, return <code>true</code> if <code>target</code> is in <code>nums</code>, or <code>false</code> if it is not in <code>nums</code>.

You must decrease the overall operation steps as much as possible.

<code>nums</code> is guaranteed to be rotated at some pivot.

解法：跟上一題類似，隻不過出現了很多相等的點，當你的start或end落在了相等點集合中的時候，你很難判斷是上升階段還是下降階段，是以我們碰到相等的點直接左移或右移。

153. Find Minimum in Rotated Sorted Array

Suppose an array of length <code>n</code> sorted in ascending order is rotated between <code>1</code> and <code>n</code> times. For example, the array <code>nums = [0,1,2,4,5,6,7]</code> might become:

<code>[4,5,6,7,0,1,2]</code> if it was rotated <code>4</code> times.

<code>[0,1,2,4,5,6,7]</code> if it was rotated <code>7</code> times.

Notice that rotating an array <code>[a[0], a[1], a[2], ..., a[n-1]]</code> 1 time results in the array <code>[a[n-1], a[0], a[1], a[2], ..., a[n-2]]</code>.

Given the sorted rotated array <code>nums</code> of unique elements, return the minimum element of this array.

You must write an algorithm that runs in <code>O(log n) time.</code>

<code>n == nums.length</code>

All the integers of <code>nums</code> are unique.

<code>nums</code> is sorted and rotated between <code>1</code> and <code>n</code> times.

154. Find Minimum in Rotated Sorted Array II

Hard

2345345Add to ListShare

Suppose an array of length <code>n</code> sorted in ascending order is rotated between <code>1</code> and <code>n</code> times. For example, the array <code>nums = [0,1,4,4,5,6,7]</code> might become:

<code>[4,5,6,7,0,1,4]</code> if it was rotated <code>4</code> times.

<code>[0,1,4,4,5,6,7]</code> if it was rotated <code>7</code> times.

Given the sorted rotated array <code>nums</code> that may contain duplicates, return the minimum element of this array.

You must decrease the overall operation steps as much as possible.

解法：需要類似上上一道題，遇到重複的左移或者右移，另外如果開頭結尾相等的，直接左移

278. First Bad Version

Easy

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have <code>n</code> versions <code>[1, 2, ..., n]</code> and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API <code>bool isBadVersion(version)</code> which returns whether <code>version</code> is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

4. Median of Two Sorted Arrays

Given two sorted arrays <code>nums1</code> and <code>nums2</code> of size <code>m</code> and <code>n</code> respectively, return the median of the two sorted arrays.

The overall run time complexity should be <code>O(log (m+n))</code>.

<code>nums1.length == m</code>

<code>nums2.length == n</code>

1.保證第一個數組長度小于等于第二個數組，這樣對第一個數組無論如何切分，第二個數組切分點永遠不會越界

2.計算第二個數組的切分點會比較tricky ,int y = (m+n+1)/2 - x 得通過舉例得出

367. Valid Perfect Square

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Follow up: Do not use any built-in library function such as <code>sqrt</code>.

這個題的坑點：num過大時很容易越界，是以mid要定義為long類型

69. Sqrt(x)

Given a non-negative integer <code>x</code>, compute and return the square root of <code>x</code>.

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

Note: You are not allowed to use any built-in exponent function or operator, such as <code>pow(x, 0.5)</code> or <code>x ** 0.5</code>.

Example 1:

Medium

You are given an array of <code>intervals</code>, where <code>intervals[i] = [starti, endi]</code> and each <code>starti</code> is unique.

The right interval for an interval <code>i</code> is an interval <code>j</code> such that <code>startj</code><code> >= endi</code> and <code>startj</code> is minimized.

Return an array of right interval indices for each interval <code>i</code>. If no right interval exists for interval <code>i</code>, then put <code>-1</code> at index <code>i</code>.

<code>intervals[i].length == 2</code>

The start point of each interval is unique.