admin 管理员组

文章数量: 887016

二分查找及其变种

文章目录

  • 二分查找及其变种
  • 标准二分
  • 四种变种
    • 查找第一个等于
    • 查找最后一个等于
    • 查找第一个≥
    • 查找最后一个≤

二分查找及其变种

标准二分

  • 初始化：int left = 0, right = nums.length - 1

  • 循环遍历：为什么是left<=right

    - 因为初始化[left,right]是两端闭区间，假如遍历结束是[left=right]=[2,2],说明至少还有一个数2是可以遍历到的，所以是left<=right才能保证全部数据被搜索过一遍；另外一个思维是由于初始条件是两端闭区间，只有当[3,2]这种left>right出现才说明没有元素可以被搜索了！

    - 如果实在是想写成left<right,最后再加上return nums[left]==target?left:-1就行

public static int binarySearch(int[] nums, int target) {if (nums == null || nums.length == 0) {return -1;}int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1;
}

四种变种

查找第一个等于

// 二分变种1:优化后的写法，强烈不推荐这么写，因为很难记
public int search1(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;}}// 循环跳出，左指针来到第一个target位置没越界且等于target，就返回midif (left < nums.length && nums[left] == target) {return left;} return -1;
} 

// 最容易理解的写法
public int search1(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 (mid == 0 || nums[mid - 1] != target) {return mid;} else {right = mid - 1;}}}return -1;
}

查找最后一个等于

// 二分变种2:数组升序有重复值，查找最后一个值等于给定值的坐标
public int search2(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 (mid == nums.length - 1 || nums[mid + 1] != target) {return mid;} else {left = mid + 1;}}}return -1;
}

查找第一个≥

// 二分变种3:数组升序有重复值，查找第一个>=给定值的下标
public int search3(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) {if (mid == 0 || nums[mid - 1] < target) {return mid;} else {right = mid - 1;}}}return -1;
}

查找最后一个≤

// 二分变种4:数组升序有重复值，查找最后一个<=给定值的下标
public int search4(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) {if (mid == nums.length - 1 || nums[mid + 1] > target) {return mid;} else {left = mid + 1;}}}return -1;
}

本文标签： 二分查找及其变种

版权声明：本文标题：二分查找及其变种 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732361412h1535321.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。