思路：

先豎著二分，找到所在行，再橫著二分，找到所在列。

class Solution {// 先豎著二分，再橫著二分public boolean searchMatrix(int[][] matrix, int target) {int n = matrix.length;int m = matrix[0].length;int top = 0;int bottom = n - 1;int row = 0;while (top <= bottom) {row = top + ((bottom - top) >> 1);if (matrix[row][0] == target) {return true;} else if (matrix[row][0] > target) {bottom = row - 1;} else if (matrix[row][0] < target) {if (row == n - 1 || matrix[row + 1][0] > target) {break;}top = row + 1;}}int left = 0;int right = m - 1;while (left <= right) {int mid = left + ((right - left) >> 1);if (matrix[row][mid] == target) {return true;} else if (matrix[row][mid] > target) {right = mid - 1;} else if (matrix[row][mid] < target) {left = mid + 1;}}return false;}
}

思路：

flatten成一維。

關鍵：計算當前mid在矩陣中的什么位置int x = matrix[mid / m][mid % m];

class Solution {// 思路：flatten成一維的public boolean searchMatrix(int[][] matrix, int target) {int n = matrix.length;int m = matrix[0].length;int left = 0;int right = n * m - 1;while (left <= right) {int mid = left + ((right - left) >> 1);// 關鍵：計算當前mid在矩陣中的什么位置int x = matrix[mid / m][mid % m];if (x == target) {return true;}if (x < target) {left = mid + 1;} else {right = mid - 1;}}return false;}
}

思路：

排除法。

從右上角開始比較。

如果右上角元素小于target，那么這一行直接丟棄，i++，下一行。

如果右上角元素大于target，那么到了所在行了，j–，往左走到盡頭。

class Solution {// 排除法public boolean searchMatrix(int[][] matrix, int target) {int n = matrix.length;int m = matrix[0].length;// 從右上角開始int i = 0;int j = m - 1;// 直到左下角while (i < n && j >= 0) {if (matrix[i][j] == target) {return true;}// 這里是右上角元素，證明這一行剩余元素全部小于 target，排除if (matrix[i][j] < target) {i++;} else {// 到所在行了，往左走。j--;}}return false;}
}

思路：

多次二分：

先找到任意一個target的索引，從當前位置，往左往右不斷二分找target，直到找到最左和最右值。

class Solution {public int[] searchRange(int[] nums, int target) {int n = nums.length;int[] res = { -1, -1 };int mid = findIndex(nums, 0, n - 1, target);if (mid == -1) {return res;} else {res[0] = mid;res[1] = mid;}int left = mid;int right = mid;while (left != -1 || right != -1) {left = findIndex(nums, 0, left - 1, target);res[0] = left != -1 ? left : res[0];right = findIndex(nums, right + 1, n - 1, target);res[1] = right != -1 ? right : res[1];}return res;}private int findIndex(int[] nums, int begin, int end, int target) {int left = begin;int right = end;while (left <= right) {int mid = left + ((right - left) >> 1);if (nums[mid] == target) {return mid;} else if (nums[mid] < target) {left = mid + 1;} else if (nums[mid] > target) {right = mid - 1;}}return -1;}
}

思路：

兩次二分。

一次尋找最左的值為target的值

第二次尋找最左的，值為target+1的值。找不到不要緊，是那個位置就行了。減一就是target的最右邊。

class Solution {public int[] searchRange(int[] nums, int target) {int start = findLeftest(nums, target);if (start == nums.length || nums[start] != target) {return new int[] { -1, -1 };}int end = findLeftest(nums, target + 1) - 1;return new int[] { start, end };}private int findLeftest(int[] nums, int target) {int left = 0;int right = nums.length - 1;while (left <= right) {int mid = left + ((right - left) >> 1);if (nums[mid] >= target) {right = mid - 1;} else {left = mid + 1;}}return left;}
}

思路：

兩次二分。

第一次，先找到最小值的點，把它劃分成兩段，這兩段都是單調的，可以用二分了。

從這兩段里面分別二分，尋找target。

class Solution {public int search(int[] nums, int target) {int n = nums.length;int i = findMin(nums);if (target > nums[n - 1]) { // target 在第一段return lowerBound(nums, -1, i, target); // 開區間 (-1, i)}// target 在第二段return lowerBound(nums, i - 1, n, target); // 開區間 (i-1, n)}// 153. 尋找旋轉排序數組中的最小值（返回的是下標）private int findMin(int[] nums) {int n = nums.length;int left = -1;int right = n - 1; // 開區間 (-1, n-1)while (left + 1 < right) { // 開區間不為空int mid = left + ((right - left) >> 1);if (nums[mid] < nums[n - 1]) {right = mid;} else {left = mid;}}return right;}// 有序數組中找 target 的下標private int lowerBound(int[] nums, int left, int right, int target) {while (left + 1 < right) { // 開區間不為空// 循環不變量：// nums[right] >= target// nums[left] < targetint mid = left + ((right - left) >> 1);if (nums[mid] >= target) {right = mid; // 范圍縮小到 (left, mid)} else {left = mid; // 范圍縮小到 (mid, right)}}return nums[right] == target ? right : -1;}
}