今天在公司午休时，做了到leetcode题，下班回家后又做了几道类似的题目，今天一共做了4道题啦！！！！！对二分算法也更深入的了解啦，不过那些时间复杂度还是有点搞不懂。一步一步来吧OvO.
题目是在搜索旋转排序数组；
假设一个升序的数组，在某一节点进行旋转，求给定数值的位置索引，若没有，则返回-1。
注意点：数组中不存在重复数据，算法时间复杂度必须是O（log n）。
示例1：
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
解释1:
0在数组中的位置是4，即nums[4]=0;
示例2：
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1
解释2:
数组中没有3，返回-1；
题解：
这道题可以用二分来解决，分三种情况讨论：
第一种情况，中间值等于给定值，直接返回中间值；
第二种情况，右边有序，且给定值在右边，直接套用基本二分法来求给定值位置，
第三种情况，左边有序，且给定值在左边，也直接套用基本二分法来求给定值位置；
代码如下：
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
|
package solution;
import java.util.*;
import java.math.*;
class solution {
public int search(int[] nums, int target) {
int r = nums.length - 1;
int l = 0;
while (l <= r) {
int mid = (r - l) / 2 + l;
System.out.print(mid);
if (nums[mid] == target)
return mid;
else if (nums[mid] < nums[r]) {
if (nums[mid] < target && target <= nums[r])
l = mid + 1;
else
r = mid - 1;
} else {
if (target >= nums[l] && target < nums[mid])
r = mid - 1;
else
l = mid + 1;
}
}
return -1;
}
public static void main(String[] args) {
solution s = new solution();
int[] b = { 4, 5, 6, 7, 0, 1, 2 };
int a = 0;
System.out.print(s.search(b, a));
}
}
|
