第三章：二分查找
1、Sqrt_x
问题：
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4
输出：2
示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
1 package LeetCode.test3_erfenchazhao; 2 3 public class ques_69_Sqrt_x { 4 public static void main(String[] args) { 5 System.out.println(mySqrt(2147395599)); //46339 6 // System.out.println(mySqrt(8)); 7 } 8 9 public static int mySqrt(int x) { 10 if (x == 0) { 11 return 0; 12 } 13 int left = 1; 14 int right = x; 15 while (left <= right) { 16 int mid = left + (right - left) / 2; 17 int sqrt = x / mid; 18 if (sqrt == mid) { // x/mid与mid相比 -> x与mid*mid相比 19 return mid; 20 } else if (sqrt < mid) { 21 right = mid - 1; 22 } else { 23 left = mid + 1; 24 } 25 } 26 return right; // 等价于(left - 1) 27 } 28 }
2、在排序数组中查找元素的第一个和最后一个位置
问题：
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
思路：要找到某个区间，肯定要进行两边的二分查找，可以定义一个函数binarySearch，找左边索引靠target，找右边索引靠target + 1即可很好的解决这个问题。
1 package LeetCode.test3_erfenchazhao; 2 3 import java.util.Arrays; 4 5 public class ques_34_在排序数组中查找元素的第一个和最后一个位置 { 6 public static void main(String[] args) { 7 int[] nums = {5, 7, 7, 8, 8, 10}; 8 int target = 8; 9 System.out.println(Arrays.toString(searchRange(nums, target))); 10 // System.out.println(binarySearch(nums, 8)); 11 // System.out.println(binarySearch(nums, 9)); 12 13 } 14 15 public static int[] searchRange(int[] nums, int target) { 16 if (nums.length == 0) { 17 return new int[]{-1, -1}; 18 } 19 int a = binarySearch(nums, target); 20 int b = binarySearch(nums, target + 1); 21 if (nums.length==a||nums[a]!=target){ 22 return new int[]{-1, -1}; 23 }else { 24 if (nums[b]==target){ 25 return new int[]{a,b}; 26 }else { 27 return new int[]{a,b-1}; 28 } 29 } 30 } 31 32 public static int binarySearch(int[] nums, int target) { 33 int left = 0; 34 int right = nums.length - 1; 35 while (left < right) { 36 int mid = left + ((right - left) >> 1); 37 if (nums[mid] < target) { 38 left = mid + 1; 39 } else { 40 right = mid; 41 } 42 } 43 return right; // 等价于left 44 } 45 }
3、搜索旋转排序数组II
问题：已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。
例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。
给你旋转后的数组nums和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。
示例 1：
输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true
示例 2：
输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false
1 package LeetCode.test3_erfenchazhao; 2 3 public class ques_81_搜索旋转排序数组II { 4 public static void main(String[] args) { 5 // int[] nums = {2, 5, 6, 0, 0, 1, 2}; 6 int[] nums = {1, 1, 1, 1, 1, 1, 1, 2, 1}; 7 // int target = 0; 8 int target = 2; 9 System.out.println(search(nums, target)); 10 } 11 12 public static boolean search(int[] nums, int target) { 13 int start = 0; 14 int end = nums.length - 1; 15 while (start <= end) { 16 int mid = start + ((end - start) >> 1); 17 if (nums[mid] == target) { 18 return true; 19 } 20 if (nums[mid] == nums[start]) { //无法判断哪个区间是增序的 21 start++; 22 } else if (nums[mid] <= nums[end]) { //右边是有序的 23 if (target > nums[mid] && target <= nums[end]) { 24 start = mid + 1; 25 } else { 26 end = mid - 1; 27 } 28 } else { //左边是有序的 29 if (target >= nums[start] && target < nums[mid]) { 30 end = mid - 1; 31 } else { 32 start = mid + 1; 33 } 34 } 35 } 36 return false; 37 } 38 }
4、寻找旋转排序数组中的最小值II
问题：已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,4] 若旋转 7 次，则可以得到 [0,1,4,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 = [1,3,5]
输出：1
示例 2：
输入：nums = [2,2,2,0,1]
输出：0
1 package LeetCode.test3_erfenchazhao; 2 3 public class ques_154_寻找旋转排序数组中的最小值II { 4 public static void main(String[] args) { 5 int[] nums = {1,3,5}; 6 System.out.println(findMin(nums)); 7 } 8 9 public static int findMin(int[] nums) { 10 int start = 0; 11 int end = nums.length - 1; 12 int min = Integer.MAX_VALUE; 13 while (start <= end) { 14 int mid = start + ((end - start) >> 1); 15 if (nums[mid] == nums[start]) { 16 start++; 17 min = Math.min(min, nums[mid]); 18 } else if (nums[mid] <= nums[end]) { 19 min = Math.min(min, nums[mid]); 20 end = mid - 1; 21 } else { 22 min = Math.min(min, nums[start]); 23 start = mid + 1; 24 } 25 } 26 return min; 27 } 28 }
5、有序数组中的单一元素
问题：
给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。
示例 1:
输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2
示例 2:
输入: nums = [3,3,7,7,10,11,11]
输出: 10
1 package LeetCode.test3_erfenchazhao; 2 3 public class ques_540_有序数组中的单一元素 { 4 public static void main(String[] args) { 5 int[] nums1 = {1, 1, 2, 3, 3, 4, 4, 8, 8}; 6 int[] nums2 = {1, 1, 3, 3, 4, 4, 5, 8, 8}; 7 System.out.println(singleNonDuplicate(nums1)); 8 System.out.println(singleNonDuplicate(nums2)); 9 } 10 11 public static int singleNonDuplicate(int[] nums) { 12 int start = 0; 13 int end = nums.length - 1; 14 while (start < end) { 15 int mid = start + ((end - start) >> 1); 16 if (mid % 2 == 1) { // 只遍历偶数下标,控制遍历的mid都是偶数下标 17 mid--; 18 } 19 if (nums[mid] == nums[mid + 1]) { // 在未遇到目标元素的情况下，nums[mid] == nums[mid+1] 20 start += 2; 21 } else { // 如果不等于那说明目标元素在左侧 22 end = mid; 23 } 24 } 25 return nums[end]; // 等价于nums[start]; 26 } 27 }