Search insert position @leetcode

leetcode原題位址：https://oj.leetcode.com/problems/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

題目含義解釋：

題目說的是給你一個有序數組，和一個目标元素，如果目标元素能找到，則傳回它的下标，如果沒有，則傳回它在序列中有可能的下标。

解題報告：

1、題目含義其實就是二分查找算法（或折半搜尋算法）的定義。

2、維基百科是這麼定義的：

二分查找算法，又稱折半搜尋算法，是一種在有序數組中查找某一特定元素的搜尋算法

3、舉出的四個示例的意思是這樣的：

[1,3,5,6], 5 → 2   目标元素5在數組中的下标是2, 說明該數組是從下标0開始算起

[1,3,5,6], 2 → 1   目标元素2，雖不在數組中，但是因為它是個有序數組，是以它有可能在元素1和元素3之間，而元素1的下标是0，是以目标元素2如果也在數組中的話，那它有可能的下标就是1

[1,3,5,6], 7 → 4  目标元素7，雖不在數組中，但是因為它是個有序數組，是以它有可能在元素6之後，而元素6的下标是3，則7的下标有可能是4

[1,3,5,6], 0 → 0  目标元素0，雖不在數組中，但是因為它是個有序數組，是以它有可能在元素1之前，也就是在整個數組的最前面，而按示例1得到，數組是從下标0開始的，是以目标元素0的下标就應該是0

4、好了，從前面3點，我們知道了完整程式該包含如下部分：

 定義一個 名為Search_insert_position的class，

4.1 裡面要定義一個數組 int[] A={1,3,5,6}  ，定義目标元素target，比如target=5

4.2  需包含二分查找算法，把它定義為方法 public int search_Insert(int[] A, int target ){}

4.3 最後要有main函數

package search;

public class Search_insert_position{
		
	//二分查找算法
	public int search_Insert(int[] A,int target){
		if (A == null || A.length == 0){
			return 0;
		}
		
		int l=0;
		int r=A.length -1;
		int mid=(1+r)/2;
		
		//記住：二分查找算法的條件是start<=end,不是start<end
		while(l<=r)
		{
			if(A[mid]==target)
				return mid;
			else {
				if(A[mid]<target)
					l=mid+1;
				else
					r=mid-1;
			}
		}
		return l;
	}
	
	//定義main函數
	public static void main(String[] args){
		
		Search_insert_position sip = new Search_insert_position();
		
		//定義一個數組A，定義名為target的目标元素
		int[] A = {1,3,5,6};
		int target = 5;
		
	
		System.out.print(sip.search_Insert(A,target));
	}
	
}