> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/1.binary-search/60search-insert-position.md).

# 60.Search Insert Position

## 1.Description(Easy)

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.

**Example**

`[1,3,5,6]`, 5 → 2

`[1,3,5,6]`, 2 → 1

`[1,3,5,6]`, 7 → 4

`[1,3,5,6]`, 0 → 0

[**Challenge**](http://lintcode.com/en/problem/search-insert-position/#challenge)

O(log(n)) time

## 2.Code

找到就返回，找不到就找最后一个比他小的数字，然后插在他后面。

注意最后比较target,start,end的大小关系，得出结论应该插在哪里。

```
public int searchInsert(int[] A, int target) {
        if(A==null || A.length==0){
            return 0;
        }

        int start=0,end=A.length-1;
        while(start+1<end){
            int mid=start+(end-start)/2;
            if(A[mid]==target){
                return mid;
            }
            else if(A[mid]>target){
                end=mid;
            }
            else{
                start=mid;
            }           
        }

        if(A[start]>=target){
            return start;
        }
        else if(A[end]>=target){
            return end;
        }
        else{
            return end+1;
        }
```