二分查找详解

大家好，欢迎来到IT知识分享网。

模板一(left <= right)：

• 二分查找的最基础和最基本的形式。
• 查找条件可以在不与元素的两侧进行比较的情况下确定（或使用它周围的特定元素）。
• 不需要后处理，因为每一步中，你都在检查是否找到了元素。如果到达末尾，则知道未找到该元素。
• 初始条件：left = 0, right = length-1
• 终止：left > right
• 向左查找：right = mid-1
• 向右查找：left = mid+1/ x 的平方根

  实现 `int sqrt(int x)` 函数。
  ​
  计算并返回 *x* 的平方根，其中 *x* 是非负整数。
  ​
  由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
  /
  public int mySqrt(int x) {
  int left = 0;
  int right = x / 2 + 1;
  long mid = 0L;
  while(left <= right){
  mid = (right – left)/2 + left;
  if(mid * mid == x){
  return (int)mid;
  }else if(mid * mid > x){
  right = (int)(mid – 1);
  }else if(mid * mid < x){
  left = (int)(mid +1);
  }
  }
  return right;
  }初始条件：left = 0, right = length终止：left == right向左查找：right = mid向右查找：left = mid+1/
  寻找峰值
  峰值元素是指其值大于左右相邻值的元素。
  ​
  给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。
  ​
  数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。
  ​
  你可以假设 nums[-1] = nums[n] = -∞。
  /
  public int findPeakElement(int[] nums) {
  int start = 0;
  int end = nums.length – 1;
  int mid = 0;
  int max = 0;
  while(start < end){
  mid = start + (end – start)/2;
  if(nums[mid] < nums[mid+1]){
  start = mid+1;
  }else{
  end = mid;
  }
  }
  return start;
  }初始条件：left = 0, right = length-1终止：left + 1 == right向左查找：right = mid向右查找：left = mid/
  在排序数组中查找元素的第一个和最后一个位置
  给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
  ​
  你的算法时间复杂度必须是 O(log n) 级别。
  ​
  如果数组中不存在目标值，返回 [-1, -1]。
  /
  public int[] searchRange(int[] nums, int target) {
  int[] res = {–1, –1};
  int n = nums.length;
  if (n == 0) return res;
  int left = 0;
  int right = n–1;
  while (left <= right){
  int mid = left + (right – left) / 2;
  if (nums[mid] == target) {
  left = mid;
  right = mid;
  while (left > 0 && nums[left] == nums[left–1]) left—;
  while (right < n – 1 && nums[right] == nums[right+1]) right++;
  res[0] = left;
  res[1] = right;
  return res;
  }
  else if (nums[mid] > target) right = mid – 1;
  else left = mid + 1;
  }
  return res;
  ​
  }