二分搜索专题2-在有序二维数组中搜索一个元素
1,设二维数组p的每行每列都按照下标递增的顺序递增。
用数学语言描述如下：p满足
(1),对任意的x1，x2，y，如果x1<x2,则p(x1,y)<p(x2,y);
(2),对任意的x，y1,y2, 如果y1<y2,则p(x,y1)<p(x,y2);
2,问题：
给定满足1的数组p和一个整数k，求是否存在x0,y0使得p(x0,y0)=k?
3,算法分析：
(1),穷举法，遍历二维数组，复杂度O(n*n)，这个方法的代码我就不写了。
(2),二分搜索，复杂度为O(n*lgn),遍历每一行，每一列采用二分搜索。
//n*O(lgn)public static Point search(int[][] p, int k) {for (int i = 0; i < p.length; i++) {int j = bSearch(p[i], 0, p[i].length, k);if (j > 0) {return new Point(i, j);}}return null;}/** * 用二分算法搜索递增数组X下标从s到e区间的值为t的元素的下标 */public static int bSearch(int[] X, int s, int e, int t) {while (s <= e) {int m = (s + e) / 2;if (X[m] == t) {return m;} else if (X[m] > t) {e = m - 1;} else {s = m + 1;}}return -1;}static class Point {int x;int y;public Point(int x, int y) {super();this.x = x;this.y = y;}}