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
| class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
for(int i=0;i<matrix.length;i++){
if(is(matrix[i],target)) return true;
}
return false;
}
Boolean is(int[] matrix,int target){
int left = 0;
int right = matrix.length-1;
while(left<=right){
int mid = (left+right)/2;
if(matrix[mid] == target) return true;
if(matrix[mid]>target){
right = mid-1;
}else{
left = mid + 1;
}
}
return false;
}
}
|
2. 再排序数组中查找元素的第一个和最后一个位置
题目如下：
解题思路：查询到元素在数组中的位置（二分查询），在对数组进行两边查找，这里可以使用双指针
代码：
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
| class Solution {
public int[] searchRange(int[] nums, int target) {
int[] ans = new int[2];
ans[0] = -1;
ans[1] = -1;
int left = 0;
int right = nums.length-1;
int index = -1;
while(left <= right){
int mid = (left+right)/2;
if(nums[mid] == target) {
index = mid;
break;
}
if(nums[mid]>target) right = mid-1;
else left = mid + 1;
}
if(index == -1) return ans;
int a = index;
while(a>=0 && nums[a]==target){a--;}
ans[0] = a+1;
a = index;
while(a<nums.length && nums[a]==target){a++;}
ans[1] = a-1;
return ans;
}
}
|
