69. x 的平方根

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4
输出: 2

题解思路：二分查找算法

  1. class Solution {
  2.     public int mySqrt(int x) {
  3.         if (x <= 1)
  4.             return x;
  5.         int left = 1, right = x;
  7.         while (left <= right) {
  8.             int mid = (right - left) / 2 + left;
  9.             int sqrt = x / mid;
  10.             if (sqrt == mid)
  11.                 return mid;
  12.             else if (sqrt > mid)
  13.                 left = mid + 1;
  14.             else if (sqrt < mid)
  15.                 right = mid - 1;
  16.         }
  17.         return right;
  18.     }
  19. }

关键点：1、采用x/mid的方式进行比较主要是为了防止整型溢出
2、最后输出的是right是因为当退出循环时，right总是更小的那个值。

744. 寻找比目标字母大的最小字母

| 给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。
在比较时，字母是依序循环出现的。举个例子：
- 如果目标字母 target = 'z' 并且字符列表为 letters = ['a', 'b']，则答案返回 'a'

示例：
输入:
letters = [“c”, “f”, “j”]
target = “a”
输出: “c” | | —- |

  1. class Solution {
  2.     public char nextGreatestLetter(char[] letters, char target) {
  3.         int n = letters.length;
  5.         int left = 0, right = n - 1;
  6.         while (left <= right) {
  7.             int mid = (right-left) / 2 + left;
  8.             if (letters[mid] <= target)
  9.                 left = mid + 1;
  10.             else
  11.                 right = mid - 1;
  12.         }
  13.         return left >= n ? letters[0] : letters[left];
  14.     }
  15. }

关键点：在最后的时候加上一层判断return left >= n ? letters[0] : letters[left];

540. 有序数组中的单一元素

给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。
示例 1:
输入: [1,1,2,3,3,4,4,8,8]
输出: 2

题解思路：我们需要查看中间的元素来判断我们的答案是在中间还是在左边或者是右边。只有一个元素有一个，其他的都是两个，意味着这个数组的长度就是奇数个。判断中间节点是和左边的相邻元素相等，还是和右边的相邻元素相等来移动mid。

153. 寻找旋转排序数组中的最小值

| 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
- 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
- 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

示例 1：
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。 | | —- |

34. 在排序数组中查找元素的第一个和最后一个位置

| 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
- 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4] | | —- |