二分查找

二分查找

经典二分查找

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

int searchInsert(vector<int> &nums, int target)
{
    int left=-1,right=nums.size(); //left和right直接将扩展下标全部包含进来
    while(left + 1 != right) //如果left并不相邻
    {
        int mid=(left+right)/2; //取中间值
        if(nums[mid]>=target) //中间值大于等于查询值，则右指针左移到中间指针
            right=mid;
        else
            left=mid; //否则左指针右移到中间指针。
        //此时可以知道right一定在最后可以成为结果位置。因为left和right指针最后一定相邻，且n指针一定和left指针重合。
        //left指针指向不会和target相等，故不管是插入位置还是相等位置，都是right指针位置
    }
    return right;
}

解析

1. 如果初始下标不是扩展位置？那就需要额外判断数组的大小，我们要依靠left + 1 != right判断，所以left和right指针不能指向同一位置或者相邻位置。那扩展位置是否会发生空指针的情况：

   1. 如果size = 0: left + 1 == right 返回位置是0，正确
   2. 如果size = 1: 如果array[0] >= target, right就会移动到0的位置. 正确,如果小于,right继续待在数列的end()位置.
   3. 如果size > 1: 显然成立. 所以任何情况下都不会发生指针指空的问题.

2. 为什么需要nums[mid]>=target? 我们在设定right时,需要保证right最后指向的数据就算不是那个值, 也一定是离那个值最近的大值.

3. left和right逼近的过程中, 一定会遇到left和right相邻的局面, 此时right一定指向的是那个>=的值. 因为我们最终是要输出right值.

平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留整数部分 ，小数部分将被舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

class Solution {
public:
    int mySqrt(int x) {
        int left = 1;
        int right = x > 46341 ? 46341 : x;
        if(right <= 1) return right;
        while (left + 1 != right){
            int mid = (left + right) / 2;
            if(mid * mid > x) right = mid;
            else left = mid;
        }
        return left;
    }
};

找到错误版本

int firstBadVersion(int n) {
    int left = 0;
    int right = n;
    while(left + 1 != right){
        int mid = (left + right) / 2;
        if(isBadVersion(mid)) right = mid;
        else left = mid;
    }
    return right;
}

找到最小的大值

char nextGreatestLetter(vector<char> &letters, char target) {
  int left = -1;
  int right = letters.size() - 1;
  while (left + 1 != right) {
    int mid = (left + right) / 2;
    if (letters[mid] <= target)
      left = mid;
    else
      right = mid;
  }
  if(letters[right] <= target) return letters[0];
  return letters[right];
}