題目:Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order ofO(logn).
If the target is not found in the array, return[-1, -1]
.
For example,
Given[5, 7, 7, 8, 8, 10]
and target value 8,
return[3, 4]
.
解題思路:題意為在一個有序數組中尋找指定值的起始位置和結束位置,因為題目要求時間復雜度為O(logn),故而想到使用二分查找法。
示例代碼:
public class Solution { public int[] searchRange(int[] nums, int target) { int[] result=new int[]{-1,-1}; int start=0; int end=nums.length-1; while(start<=end) { int middle=(start+end)>>1; int middleValue=nums[middle]; if(middleValue==target) { //找到目標值後,先搜索其左邊有沒有與目標值相等的數,取其最左邊的索引值放入result中,同理再搜索其最右邊 int i=middle; while((i-1)>=0&&nums[i-1]==target) { i--; } result[0]=i; int j=middle; while((j+1)