題目: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)