p34

发表于 | 分类于 |

LeetCode 34 Search for a Range 题解

1.题目：

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 of O(log n).
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].

题意：

输入一个有序数组，查找某个目标数的起始。

2.解题思路:

先用二分找到一个目标数，然后对其进行左右延展。

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 

public class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ans = { -1, -1 };
		if (nums == null)
			return ans;
		int len = nums.length;
		int left = 0;
		int right = nums.length;

		if (nums[0]==target&&nums[right-1]==target) return new int[]{0,len-1};
		while (left < right) {
			int mid = (right - left) / 2 + left;

			if (nums[mid] == target) {

				left = mid;
				right = mid;
				while (left >=0 && nums[left] == target)
					left--;
				while (right < len && nums[right] == target)
					right++;
				ans[0] = left + 1;
				ans[1] = right - 1;
				break;
			}
			if (nums[mid] > target) {
				right = mid;

			}
			if (nums[mid] < target) {
				left = mid + 1;

			}

		}
		return ans;
    }
}

4.一些总结：宛如智障的拿mid 与target比较调了好久bug.TUT