p35

发表于 | 分类于 |

LeetCode 35 Search Insert Position 题解

1.题目：

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

题意：

输入一个有序数组，查找某个目标数的插入位置。

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
 

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

		if (nums[0] > target)
			return 0;
		if (nums[len - 1] < target)
			return len;

		while (left < right) {
			int mid = (right - left) / 2 + left;

			if (nums[mid] == target) {

				return mid;
			}
			if (nums[mid] > target) {
				right = mid;

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

			}
			// System.out.println(left+"  "+right+"  "+mid);

		}
		while (left > 0 && nums[left] > target)
			left--;
		return left + 1;
    }
}

4.一些总结：