給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。

你可以假設(shè)數(shù)組中無(wú)重復(fù)元素。

示例 1:

輸入: [1,3,5,6], 5

輸出: 2

示例?2:

輸入: [1,3,5,6], 2

輸出: 1

示例 3:

輸入: [1,3,5,6], 7

輸出: 4

示例 4:

輸入: [1,3,5,6], 0

輸出: 0

??int?searchInsert(vector<int>&?nums,?int?target)?{

????????int?l?=?0;

????????int?r?=?nums.size()-1;

????????int?mid;

????????while(l?<=?r)

????????{

????????????mid?=?(l+r)/2;

????????????if(nums[mid]?==?target)

????????????????return?mid;

????????????else?if(nums[mid]?>?target)

????????????????r?=?mid?-?1;

????????????else?if(nums[mid]?<?target)

????????????????l?=?mid?+?1;

????????}

????????return?l;

????}

另一種：

int?searchInsert(vector<int>&?nums,?int?target)?{

????????int?index?=?-1;

????????int?l?=?0;

????????int?r?=?nums.size()-1;

????????int?mid;

????????while(index?==?-1)

????????{

????????????mid?=?(l+r)/2;

????????????if(nums[mid]?==?target)

????????????????return?mid;

????????????else?if(nums[mid]?>?target)

????????????{

????????????????if(mid?==?0?||?target?>?nums[mid-1])

????????????????????index?=?mid;

????????????????r?=?mid?-?1;

????????????}

????????????else?if(nums[mid]?<?target)

????????????{

????????????????if(mid?==?nums.size()?-?1?||?target?<?nums[mid?+?1])

????????????????????index?=?mid?+?1;

????????????????l?=?mid?+?1;

????????????}

????????}

????????return?index;

????}