二分查找入门——第4天

• 一、69. x 的平方根
• • 1. 题目
  • 2.思路
  • 3.题解
  • 4.结果
• 二、744. 寻找比目标字母大的最小字母
• • 1.题目
  • 2.思路
  • 3.题解
  • 4.结果

https://leetcode.cn/problems/sqrtx/

这题其实与 力扣的 367. 有效的完全平方数 十分相似。
使用二分查找,只要找到满足(x+0.0)/mid >= mid && (x+0.0) / (mid+1) < (mid+1) 的数就返回mid。

class Solution {
    public int mySqrt(int x) {
        if(x<= 1){
            return x;
        }
        int left = 1;
        int right = x/2;
        while(right >= left){
            int mid = left + (right-left)/2;
            if((x+0.0)/mid >= mid && (x+0.0) / (mid+1) < (mid+1)){
                return mid;
            }
            if((x+0.0)/mid > mid){
                left = mid + 1;
            }
            if((x+0.0)/mid < mid){
                right = mid - 1;
           }
        }
        return -1;
    }
}

https://leetcode.cn/problems/find-smallest-letter-greater-than-target/

二分查找,比目标字母大就在左部分用二分查找,比目标字母小就在右部分用二分查找,找到就返回。找不到就返回字符列表的首字母。

class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        if(target >= letters[letters.length-1] )
            return letters[0];
        int left = 0;
        int right = letters.length - 1;
        while(right >= left){
            int mid = left + (right-left)/2;
            if(letters[mid] > target){
                right = mid - 1;
            }
            else{
                left = mid + 1;
            }
        }
        return letters[right+1];
    }
}