常青笔记
- 优点是比较次数少，查找速度快，平均性能好；
- 缺点是要求待查表为有序表，且插入删除困难。 因此，二分查找方法适用于不经常变动而查找频繁的有序列表。 使用条件：查找序列是顺序结构，有序。
- 使用总结， 注意二分查询的开闭区间问题即可。如 [] 左右闭区间
摘要
/**
* 二分查找 * @param array 待查询数据，必须为一个有序数组
* * @return 无查询，返回-1
*/
public static int binarySearch(int[] array, int searchValue) {
if (array.length == 0) {
return -1;
}
if (searchValue > array[array.length - 1] || searchValue < array[0]) {
return -1;
}
// 左右区间 []
int start = 0;
int end = array.length - 1;
int mid = 0;
// 因为是闭期间，所以这里要判断end
while (start <= end) {
mid = (start + end) >>> 1; // 这里有多种写法，要注意越界问题。
// 说明在右半边
if (searchValue > array[mid]) {
start = mid + 1; // 注意是否需要加1，避免死循环
} else if (searchValue < array[mid]) {
end = mid - 1;
} else {
return mid;
}
}
return -1;
}关键点
- 掌握二分法的重点，在于要记住开闭区间。如左右开区间。
- 死循环和越界问题
- start<=end ,要注意是否需要 ”=“号。
- 取中值的时候，越界问题。应该使用 (start + end) >>>1 或者 start + (end-start)/2。
- 如果searchValue > array[mid] 要注意是否需要 +1
题集
搜索二维矩阵（#74）
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 3 输出：true
解析: 将二维数组当成一个一维数组。
行列坐标为(row, col)的元素，展开之后索引下标为idx = row * n + col；反过来，对于一维下标为idx的元素，对应二维数组中的坐标就应该是： row = idx / n; col = idx % n;
public class SearchMatrix {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
if (m == 0) return false;
int n = matrix[0].length;
int left = 0;
int right = m * n - 1;
// 二分查找，定义左右指针
while (left <= right) {
int midIdx = (left + right) / 2;
int midElement = matrix[midIdx / n][midIdx % n];
if (midElement < target)
left = midIdx + 1;
else if (midElement > target)
right = midIdx - 1;
else
return true; // 找到target
}
return false;
}
}