4.二分查找
单调一维数组的二分查找及其变种：
一.二分查找
1.题目描述：
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
2.示例：
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
3.解:
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
}4.总结
变种（以下变种均适用于数组中存在重复值的情况）：
以"1,2,3,3,4,5"为例，记住下面这些变种
（1）模板
class Solution {
public int search(int[] array, int key) {
int left = 0;
int right = array.length - 1;
while (left <= right) {
int mid = left + (right-left) / 2;
if (array[mid] ? key) {
}
else {
}
}
return xxx;
}
}（2）关于返回left和right。
如果查找第一个XXX，返回left
如果查找最后一个XXX，返回right
（3）关于last和first以及<,>,=问题
"="
=last 查找最后一个等于key的元素 if: array[mid] <= key else: array[mid] > key return: right
first= 查找第一个等于key的元素 if: array[mid] >= key else：array[mid] < key return: left
"<" ">":
<last 查找最后一个小于key的元素 if: array[mid] < key else: array[mid] >= key return: right
first> 查找第一个大于key的元素 if: array[mid] >= key else：array[mid] < key return: left
"<=" ">="
与"="的情况完全一样，只不过"="中需要在return之前加判断语句
=last
if (right >= 0 && array[right] == key) {
return right;
}
return -1;first=
if (left < array.length && array[left] == key) {
return left;
}
return -1;单调一维数组旋转后的二分查找及其变种：
https://leetcode-cn.com/problems/search-rotate-array-lcci/solution/xuan-zhuan-shu-zu-cong-yi-dao-nan-ge-ge-dcv7a/
一.搜索旋转数组
1.题目描述：
搜索旋转数组。给定一个排序后的数组，包含n个整数，但这个数组已被旋转过很多次了，次数不详。请编写代码找出数组中的某个元素，假设数组元素原先是按升序排列的。若有多个相同元素，返回索引值最小的一个。
2.示例：
输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5
输出: 8（元素5在该数组中的索引）
3.解:
class Solution {
public int search(int[] arr, int target) {
if (arr == null || arr.length == 0) return -1;
int l = 0;
int r = arr.length - 1;
int mid;
while (l < r) {
mid = l + (r + 1 - l) / 2;
if (arr[mid] < arr[r]) r = mid;
else l = mid + 1;
}
r = l + arr.length - 1;
if(target<arr[l]) return -1;
while (l < r) {
mid = l + (r + 1 - l) / 2;
if (arr[mid % (arr.length - 1)] == target) return mid % (arr.length - 1);
else if (arr[mid % (arr.length - 1)] < target) l = mid + 1;
else if (arr[mid % (arr.length - 1)] > target) r = mid - 1;
}
return -1;
}
}4.总结
二维数组的二分查找及其变种：
一.统计有序矩阵中的负数
1.题目描述：
给你一个 m * n 的矩阵 grid，矩阵中的元素无论是按行还是按列，都以非递增顺序排列。
请你统计并返回 grid 中 负数 的数目。
2.示例：
输入：grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
输出：8
解释：矩阵***有 8 个负数。
3.解:
（1）网友答案：
class Solution {
public int countNegatives(int[][] grid) {
int num = 0;
int rowNum = grid.length;
int colNum = grid[0].length;
int leftSite =0;
int rightSite = colNum-1;
int midSite;
for(int i=0;i<rowNum;i++){
leftSite = 0;//重置左坐标为0，右坐标位置重置操作在后面
//找到当前行的第一个不是负数的元素的位置
while(leftSite<rightSite){
midSite = (leftSite+rightSite+1)/2;
if(grid[i][midSite]>=0) leftSite = midSite;
else if(grid[i][midSite]<0) rightSite = midSite-1;
}
//改变下一行右坐标的值
if(grid[i][leftSite]>=0){
num +=colNum-(leftSite+1);
rightSite = leftSite;
}
//改变下一行右坐标的值
else {
num +=(colNum-leftSite);
rightSite = leftSite-1;
}
}
return num;
}
}二.二维数组中的查找
1.题目描述：
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
2.示例：
现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
3.解:
（1）我的答案:
class Solution {
int rowNum;
int colNum;
int right;
int left;
int mid;
public boolean findNumberIn2DArray(int[][] matrix, int target) {
rowNum = matrix.length;
if (rowNum == 0) return false;
colNum = matrix[0].length;
for (int i = 0; i < rowNum; i++) {
left = 0;
right = colNum;
while (left < right) {
mid = (right + left) / 2;
if (matrix[i][mid] == target) return true;
else if (matrix[i][mid] < target) left = mid + 1;
else if (matrix[i][mid] > target) right = mid;
}
}
return false;
}
}（2）网友答案：
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
if(matrix == null || matrix.length == 0) {
return false;
}
int m = matrix.length, n = matrix[0].length;
int row = 0, col = n - 1;
while(row < m && col >= 0) {
if(matrix[row][col] > target) {
col--;
}else if(matrix[row][col] < target) {
row++;
}else {
return true;
}
}
return false;
}
}4.总结
网友的答案更好，时间复杂度仅仅为logn，而我的答案多少有点儿暴力了，时间复杂度为nlogn。网友的答案的原理时从二维数组的右上角出发，大于target则左移一位，小于target则下移一位。
其他无类型的二分查找及其变种:
一.魔术索引
1.题目描述：
在数组A[0...n-1]中，有所谓的魔术索引，满足条件A[i] = i。给定一个单调非递减整数数组，编写一种方法找出魔术索引，若有的话，在数组A中找出一个魔术索引，如果没有，则返回-1。若有多个魔术索引，返回索引值最小的一个。
2.示例：
输入：nums = [0, 2, 3, 4, 5]
输出：0
说明: 0下标的元素为0
3.解:
（1）我的答案：
class Solution {
public int findMagicIndex(int[] nums) {
int index = -1;
int right = nums.length - 1;
int left = 0;
int mid;
while (left <= right) {
mid = (right + left + 1) / 2;
if (mid < nums[mid]) right = mid - 1;
else if (nums[mid] < mid) left = mid + 1;
else if (mid == nums[mid]) {
index = mid;
right = mid - 1;
}
}
return index;
}
}（2）网友答案
class Solution {
public int findMagicIndex(int[] nums) {
for(int i=0;i<nums.length;){
if(i==nums[i]) return i;
i=Math.max(i+1,nums[i]);
}
return -1;
}
}4.总结：这个题其实是一道大题的第二小问，第一小问是严格单调递增的整数数组，第二小问就是本题，改成了不严格的递增。
在严格单调递增的情况下，我的答案是可以的，即二分查找，此时的时间复杂度时O（logn）,而第二问的目的是为了证明第二问不存在时间复杂度是O（logn）的解法，时间复杂度最小也得是O（n）。第二问采用常规的顺序遍历即可，当然也可以向网友那样采用跳跃法，都是可以的。
二.山脉数组的峰顶索引
1.题目描述：
符合下列属性的数组 arr 称为 山脉数组 ：
arr.length >= 3
存在 i（0 < i < arr.length - 1）使得：
arr[0] < arr[1] < ... arr[i-1] < arr[i]
arr[i] > arr[i+1] > ... > arr[arr.length - 1]
给你由整数组成的山脉数组 arr ，返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i 。
2.示例：
输入：arr = [0,1,0]
输出：1
3.解:
（1）网友答案：
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int l=0;
int r=arr.length-1;
int mid;
while(l<r){
mid = (l+r)/2;
if(arr[mid]>arr[mid+1]) r=mid;
else if(arr[mid]<arr[mid+1]) l=mid+1;
}
return l;
}
}class Solution {
public int peakIndexInMountainArray(int[] arr) {
for(int i =1;i<arr.length-1;i++){
if(arr[i+1]<arr[i]) return i;
}
return -1;
}
}4.总结：这道题用二分查找时间复杂比for循环遍历的时间复杂度小。
查看1道真题和解析