1-leetcode35. 搜索插入位置
注意：×
- 看Labuladong的書，知道
while的判斷符號跟left right的關系
public int searchInsert(int[] nums, int target) {int left = 0;int right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] > target) {right = mid - 1;} else if (nums[mid] < target) {left = mid + 1;}}return right+1;}
leetcode74. 搜索二維矩陣
注意：√
- 跟之前一個題目很像，這種矩陣直接從左上角或者右下角進行查找即可
public boolean searchMatrix(int[][] matrix, int target) {int n = 0;int m = matrix[0].length - 1;while (n < matrix.length && m >= 0) {if (matrix[n][m] == target){return true;} else if (matrix[n][m] > target) {m--;} else if (matrix[n][m] < target) {n++;}}return false;}
3-leetcode34. 在排序數組中查找元素的第一個和最后一個位置
注意：×
- 注意找左邊界，是right移動–這個其實沒問題
- 問題是：你移動的時候不可以
right == mid，這樣會死循環的(其實寫的時候就能發現這個問題)所以直接給變化的值，因為后面會判斷結果的 - 左邊界，最下面的判讀是判斷左邊界
- 右邊界，最下面的判斷是判斷右邊界
public int[] searchRange(int[] nums, int target) {if (nums.length == 0) {return new int[]{-1, -1};}int[] arr = new int[2];arr[0] = findLeftBound(nums, target);arr[1] = findRightBound(nums, target);return arr;}private int findRightBound(int[] nums, int target) {int left = 0;int right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {left = mid + 1;} else if (nums[mid] > target) {right = mid - 1;} else if (nums[mid] < target) {left = mid + 1;}}if (right < 0) {return -1;}return nums[right] == target ? right : -1;}private int findLeftBound(int[] nums, int target) {int left = 0;int right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {right = mid - 1;} else if (nums[mid] > target) {right = mid - 1;} else if (nums[mid] < target) {left = mid + 1;}}if (left == nums.length){return -1;}return nums[left] == target? left: -1;}
4-leetcode33. 搜索旋轉排序數組
注意：×
- 通過最左邊的數字跟
nums[mid]進行對比，可以得到左邊是 有序還是右邊是有序的 - 然后判斷target的落點
- 注意target和nums[left]的值的對比，不要漏掉相等的情況，即：
if (nums[mid] > target || nums[left] **<=** target){
public int search(int[] nums, int target) {int left = 0;int right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target){return mid;} else if (nums[left] <= nums[mid]) {// 左邊是有序的if (nums[mid] < target || nums[left] > target){left = mid + 1;}else {right = mid - 1;}} else if (nums[left] > nums[mid]) {// 右邊雖然反轉了，但是右邊是有序的if (nums[mid] > target || nums[left] <= target){right = mid - 1;}else {left = mid + 1;}}}return -1;}
5-leetcode153. 尋找旋轉排序數組中的最小值
注意：×
- 這個題不能跟上面那個題一樣比較左邊的值，會出錯，因為上面那個只要找到哪邊有序就行，但是在這題里面，有序不代表最小，
nums[mid] < nums[left]無法得到最小值的位置，可能在左邊也可能在右邊 - 因為要找最小的那個的值，沒有
target'所以調整了right的修改策略，注意注意！！！！！！！！！！ - 第一編寫反正是有點怪怪的感覺，不行就記下來吧
public int findMin(int[] nums) {int left = 0;int right = nums.length - 1;while (left < right) {int mid = left + (right - left) / 2;if (nums[right] < nums[mid]) {left = mid + 1;} else {right = mid;}}return nums[left];}
)
