二分查找作用于有序数组，内容参考极客时间《数据结构与算法之美》
常规二分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public static int binarySearch(int[] array, int k) {
if (array == null) {
return -1;
}
int left = 0;
int right = array.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (array[mid] > k) {
right = mid - 1;
} else if (array[mid] < k) {
left = mid + 1;
} else {
return mid;
}
}
return -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
| public static int binarySearch(int[] array, int k) {
if (array == null) {
return -1;
}
int left = 0;
int right = array.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (array[mid] > k) {
right = mid - 1;
} else if (array[mid] < k) {
left = mid + 1;
} else {
if (mid == 0 || array[mid - 1] != k) {
return mid;
}
right = mid - 1;
}
}
return -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
| public static int binarySearch(int[] array, int k) {
if (array == null) {
return -1;
}
int left = 0;
int right = array.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (array[mid] > k) {
right = mid - 1;
} else if (array[mid] < k) {
left = mid + 1;
} else {
if (mid == array.length - 1 || array[mid + 1] != k) {
return mid;
}
left = mid + 1;
}
}
return -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
| public static int binarySearch(int[] array, int k) {
if (array == null) {
return -1;
}
int left = 0;
int right = array.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (array[mid] >= k) {
if (mid == 0 || array[mid - 1] < k) {
return mid;
}
right = mid - 1;
} else {
left = mid + 1;
}
}
return -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
| public static int binarySearch(int[] array, int k) {
if (array == null) {
return -1;
}
int left = 0;
int right = array.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (array[mid] <= k) {
if (mid == array.length - 1 || array[mid + 1] > k) {
return mid;
}
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
|
旋转数组中查找某个值
leetcode第33题
链接
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
| public static int binarySearchInRotatedArray(int[] array, int k) {
if (array == null) {
return -1;
}
int left = 0;
int right = array.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (array[mid] == k) {
return mid;
}
if (array[left] <= array[mid]) {
if (k >= array[left] && k < array[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (k > array[mid] && k <= array[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
|
旋转数组中查找最小值
leetcode 第153题
链接
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
| public int findMin(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
if (nums.length == 1) {
return nums[0];
}
if (nums[0] <= nums[nums.length - 1]) {
return nums[0];
}
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (mid>0 && nums[mid] < nums[mid - 1]) {
return nums[mid];
}
if (nums[left] <= nums[mid]
&& nums[mid] >= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
|