LeetCode -- Search Insert Position

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


給定已排序的數組，試圖找到值為target的索引，如果沒有找到，則返回它能夠插入的位置，使得插入後數組仍為升序。


思路：


本題依然是二分法，只是要添加對插入的處理。


實現代碼：

public class Solution {
    public int SearchInsert(int[] nums, int target) 
    {
        var l = 0;
    	var r = nums.Length - 1;
    	
    	while(l < r - 1){
    		var m = (l + r) / 2;
    		
    		var i = GetEqualsIndex(target, nums, new[]{l,r,m});
    		if(i != -1){
    			return i;
    		}
    		
    		if(target > nums[m]){
    			l = m;
    		}
    		else{
    			r = m;
    		}
    	}
    	
    	var index = GetEqualsIndex(target, nums, new[]{l,r});
    	if(index != -1){
    		return index;
    	}
    	if(target < nums[l]){
    		return l > 0 ? l - 1 : 0;
    	}
    	else if(target > nums[r]){
    		return r + 1;
    	}
    	else{
    		return l + 1;
    	}
	
    }
    
    private int GetEqualsIndex(int target, int[] nums, int[] indexes)
    {
    	foreach(var i in indexes){
    		if(nums[i] == target){
    			return i;
    		}
    	}
    	
    	return -1;
    }
    
}