給定一個數值不重複的已排序陣列和目標值，題目要求找出該目標值在這個陣列中的索引位置；若找不到則回傳插入數值的正確排序位置。
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:
Input: [1,3,5,6], 5 Output: 2
Example 2:
Input: [1,3,5,6], 2 Output: 1
Example 3:
Input: [1,3,5,6], 7 Output: 4
Example 4:
Input: [1,3,5,6], 0 Output: 0
解題思路:
因為此題所提供的陣列是已排序過的陣列，所以我們可以使用二元搜尋法(Binary Search)來加快搜尋資料的速度
步驟一: 取得上(up)、下限(lo)索引
步驟二: 使用上下限索引計算出中間值位置(mid)，並將目標數值(target)跟中間值進行比較
步驟三: 當目標數值比中間值大則將下限索引位置+1，並進行上下限索引計算出中間值位置，再進行比較;如果目標數值比中間值小則將上限索引位置-1，重複進行與中間值比較，直到找到答案(target == mid)，如果區塊上下限交錯(那就表示target不存在於陣列之中)，
我們同樣可以將下限的index輸出，因為它就代表應該被插入的點。
P.S. 上下限交錯例如上限為0下限為1等狀況
using System;
namespace Search_Insert_Position
{
class Program
{
static void Main(string[] args)
{
int[] nums = new int[] { 1, 3, 5, 6 };
var result = SearchInsert(nums, 0);
Console.WriteLine(result);
}
public static int SearchInsert(int[] nums, int target)
{
if (nums.Length == 0 || nums == null)
{
return 0;
}
int mid = 0;
int lo = 0;
int up = nums.Length - 1;
while (lo <= up)
{
mid = (lo + up) / 2;
if (target == nums[mid])
{
return mid;
}
if (target > nums[mid])
{
lo = mid + 1;
}
else
{
up = mid - 1;
}
}
return lo;
}
}
}