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>The difference is that I used a loop from beginning to end and did not fully utilize the sorted condition. The optimal solution uses the dichotomy method, which is basically the algorithm in sorting.
The above is the detailed content of LeetCode & Q35-Search Insert Position-Easy. For more information, please follow other related articles on the PHP Chinese website!