二分查找模板I

二分查找模板 I

int binarySearch(vector<int>& nums, int target){
  if(nums.size() == 0)
    return -1;

  int left = 0, right = nums.size() - 1;
  while(left <= right){
    // Prevent (left + right) overflow
    int mid = left + (right - left) / 2;
    if(nums[mid] == target){ return mid; }
    else if(nums[mid] < target) { left = mid + 1; }
    else { right = mid - 1; }
  }

  // End Condition: left > right
  return -1;
}

区分语法：

• 初始条件：left = 0, right = length-1
• 终止：left > right
• 向左查找：right = mid-1
• 向右查找：left = mid+1

例1：

解法1：

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        int ans = exp(0.5 * log(x));
        return ((long long)(ans + 1) * (ans + 1) <= x ? ans + 1 : ans);
    }
};

解法2：

class Solution {
public:
    //到1---x中寻找x的平方根
    int mySqrt(int x) 
    {
        int low, high, mid,ans;
        low = 0; high = x;
        while (low<= high)
        {
            mid = (low + high) / 2;
            if ((long long)mid * mid <= x)
            {
                ans = mid;
                low = mid + 1;
            }
            else
            {
                high = mid - 1;
            }
        }
        return ans;
    }
};

例2：


解法1：二分查找

class Solution {
public:
    int guessNumber(int n) {
        int l = 0;
        int r = n;
        while (l <= r)
        {
            int m = (l-r)/2 + r;
            int res = guess(m);
            if (res == 0)
            {
                return m;
            }
            else if (res < 0)
            {
                r = m-1;
            }
            else
            {
                l = m + 1;
            }
        }

        return -1;
    }
};

例3：

class Solution {
public:
    int search(vector<int>& nums, int target)
    {
        int low = 0;
        int high = nums.size() - 1;
        while (low <= high)
        {
            int mid = (low + high) / 2;
            if (nums[mid] == target)
                return mid;
            //先判断mid位于左段还是右端
            if (nums[mid] >=nums[low])//mid位于左段
            {
                //如果此时target同时满足位于左段并且小于nums[mid]的条件，说明target对应下标小于mid
                if (target >=nums[low] && target < nums[mid])
                    high = mid - 1;
                 else
                    low = mid + 1;
            }
            else //mid位于右段
            {
                if (target > nums[mid] && target <=nums[high])
                    low = mid + 1;
                else
                    high = mid - 1;
            }
        }
        return -1;
    }
};

例三的图解：