力扣100题——二分查找
搜索插入位置
题目
35. 搜索插入位置 - 力扣（LeetCode）
思路
判断nums数组是否为空，或目标值小于数组最小值，直接返回0
遍历数组判断数组中是否有目标值，若有直接返回索引；若没有，判断目标值的插入位置，nums[i]<target&&i+1<nums.length&&nums[i+1]>target；
遍历结束后若还没有结束，代表目标值大于数组中的所有元素，直接返回数组的长度
代码
public int searchInsert(int[] nums, int target) {if(nums.length==0){return 0;}if(nums[0]>target){return 0;}for(int i=0;i<nums.length;i++){if(nums[i]==target){return i;}if(nums[i]<target&&i+1<nums.length&&nums[i+1]>target){return i+1;}}return nums.length;}搜索二维矩阵
题目
74. 搜索二维矩阵 - 力扣（LeetCode）
思路
首先判断矩阵是否为空，以及目标值是否小于矩阵最小的元素。
根据矩阵的特性，先确定目标数在哪一行，再遍历该行。
代码
public boolean searchMatrix(int[][] matrix, int target) {int n = 0,m = matrix[0].length-1;for(int i=0;i<matrix.length;i++){if(matrix[i][0]==target||matrix[i][m]==target){return true;}System.out.println(matrix[i][0]+" "+matrix[i][m]);if(matrix[i][0]<target&&matrix[i][m]>target){n=i;}}System.out.println(n);for(int i=0;i<matrix[0].length;i++){if(matrix[n][i]==target){System.out.println(matrix[n][i]);return true;}}return false;}在排序数组中查找元素的第一个和最后一个位置
题目
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
思路
直接模拟就行了，没什么好说的
代码
public int[] searchRange(int[] nums, int target) {int[] res = new int[2];boolean flag = false;for(int i=0;i<nums.length;i++){if(nums[i]==target){if(flag){res[1] = i;}else{flag=true;res[0]=i;res[1]=i;}}}if(!flag){res[0]=-1;res[1]=-1;}return res;}搜索旋转排序数组
题目
33. 搜索旋转排序数组 - 力扣（LeetCode）
思路
使用二分查找处理旋转排序数组。在二分查找过程中判断在哪一部分（左半部分有序还是右半部分有序）继续查找。
- 二分查找：使用二分查找的思想，通过不断将搜索区间缩小一半来查找目标值。
- 判断有序区间：在二分查找的过程中，判断中间元素的左右哪一部分是有序的，然后根据目标值是否在有序区间内，决定搜索哪一边。
- 时间复杂度：优化后的时间复杂度为
O(log n)。
代码
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;}// 判断哪一部分是有序的if (nums[left] <= nums[mid]) {// 左半部分有序if (nums[left] <= target && target < nums[mid]) {right = mid - 1; // 目标值在左半部分} else {left = mid + 1; // 目标值在右半部分}} else {// 右半部分有序if (nums[mid] < target && target <= nums[right]) {left = mid + 1; // 目标值在右半部分} else {right = mid - 1; // 目标值在左半部分}}}// 如果没找到，返回 -1return -1;
}
寻找旋转排序数组的最小值
题目
153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）
思路
- 二分查找：在每次迭代时，比较
mid和right元素，判断最小值位于左半部分还是右半部分。通过这种方式逐步缩小搜索范围。 - 退出条件：当
left和right相等时，退出循环，left就是最小值所在的位置。 - 时间复杂度：二分查找的时间复杂度为
O(log n)，相较于线性遍历的O(n)，在大数据规模时效率更高。
代码
public int findMin(int[] nums) {int left = 0;int right = nums.length - 1;// 使用二分查找while (left < right) {int mid = left + (right - left) / 2;// 如果中间值大于右边界，说明最小值在右半部分if (nums[mid] > nums[right]) {left = mid + 1;} // 否则，最小值在左半部分或是mid本身else {right = mid;}}// 最终 left 指向最小值return nums[left];
}