【演演算法】在排序陣列中查詢元素的開始位置和結束位置

【演演算法】在排序陣列中查詢元素的開始位置和結束位置

一.問題描述：

1.輸入：輸入一個已經升序排列的整數型陣列arr和一個目標值target。

2.輸出：輸出這個目標值target在陣列中的開始位置和結束位置的索引。若target在陣列中不存在，則返回[-1,-1]。

3.比如：輸入{5,7,7,8,8,10}，target=8 ;輸出[3,4]

​ 輸入{5,7,7,8,8,10}，target=6;輸出[-1,-1]

​ 輸入{5,7,7,8,8,810}，target=8;輸出[3,5]

​ 輸入{5,7,7,8,8,8,10}，target=10;輸出[6,6]

​ 輸入{5,7,7,8,8,8,10}，target=5;輸出[0,-1]

二.問題解答：

方法:線性掃描(即依次遍歷陣列)

第一次遍歷從左往右遍歷，直到找到開始位置的索引值；第二次遍歷從右往左遍歷，直到找到結束位置的索引值。

三.演演算法分析：

1.時間複雜度為O(N)，額外空間複雜度為O（1）。

程式碼如下

import java.util.Arrays;
import java.util.Scanner;
/*
 * 問題：在排序陣列中查詢元素的開始位置和結束位置
 */
public class SearchRange {
	public static void main(String[] args) {
		Scanner in =new Scanner(System.in);
		String str=in.nextLine();
		int target=in.nextInt();
		String [] strArray=str.split(",");
		int[] arr=new int[strArray.length];
		for(int i=0;i<arr.length;i++) {
			arr[i]=Integer.valueOf(strArray[i]);
		}
		int[] result= SearchRange(arr, target);
		System.out.println(Arrays.toString(result));
	}
	public static int [] SearchRange(int []arr,int target) {
		int[] result= {-1,-1};
		for(int i=0;i<arr.length;i++) {
			if(arr[i]==target) {
				result[0]=i;
				break;
			}
		}
		if(result[0]==-1) {
			return result;
		}
		for(int j=arr.length-1;j>0;j--) {
			if(arr[j]==target) {
				result[1]=j;
				break;
			}
		}
		return result;
	}
}