Leetcode: Search Insert Position

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

很简单的题目，一次过，注意为数组空的时候，应返回0而非null

 1 public class Solution {
 2     public int searchInsert(int[] A, int target) {
 3         int i;
 4         if (A.length == 0) return 0;
 5         for (i=0; i<A.length; i++){
 6             if (target <= A[i]){
 7                 return i;
 8             }
 9         }
10         return A.length;
11     }
12 }

binary search: 就是当循环结束时，如果没有找到目标元素，那么l一定停在恰好比目标大的index上，r一定停在恰好比目标小的index上

 1 public int searchInsert(int[] A, int target) {
 2     if(A == null || A.length == 0)
 3     {
 4         return 0;
 5     }
 6     int l = 0;
 7     int r = A.length-1;
 8     while(l<=r)
 9     {
10         int mid = (l+r)/2;
11         if(A[mid]==target)
12             return mid;
13         if(A[mid]<target)
14             l = mid+1;
15         else
16             r = mid-1;
17     }
18     return l;
19 }