LeetCode & Q35-搜尋插入位置-簡單

Array Binary Search

#Description:

Given a sorted array 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 may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

my Solution:

<code class="sourceCode java"><span class="kw">public</span> <span class="kw">class</span> Solution {
    <span class="kw">public</span> <span class="dt">int</span> <span class="fu">searchInsert</span>(<span class="dt">int</span>[] nums, <span class="dt">int</span> target) {
        <span class="dt">int</span> i = <span class="dv">0</span>;
        <span class="kw">for</span>(i = <span class="dv">0</span>; i < nums.<span class="fu">length</span>; i++) {
            <span class="kw">if</span>(target <= nums[i])
                <span class="kw">break</span>;
        }
        <span class="kw">if</span>(i < nums.<span class="fu">length</span>)
            <span class="kw">return</span> i;
        <span class="kw">else</span>
            <span class="kw">return</span> i++;
    }
}</code>

Best Solution:

<code class="sourceCode java"><span class="kw">public</span> <span class="dt">int</span> <span class="fu">searchInsert</span>(<span class="dt">int</span>[] A, <span class="dt">int</span> target) {
    <span class="dt">int</span> low = <span class="dv">0</span>, high = A.<span class="fu">length</span><span class="dv">-1</span>;
    <span class="kw">while</span>(low<=high){
        <span class="dt">int</span> mid = (low+high)/<span class="dv">2</span>;
        <span class="kw">if</span>(A[mid] == target) <span class="kw">return</span> mid;
        <span class="kw">else</span> <span class="kw">if</span>(A[mid] > target) high = mid<span class="dv">-1</span>;
        <span class="kw">else</span> low = mid<span class="dv">+1</span>;
    }
    <span class="kw">return</span> low;
}</code>

差別就在於，我用的是從頭到尾循環，沒有完全利用好已排序這個條件。最優解用的是二分法，基本上就是排序裡的演算法。

以上是LeetCode & Q35-搜尋插入位置-簡單的詳細內容。更多資訊請關注PHP中文網其他相關文章！