在排序数组中查找数字0～n1中缺失的数字

统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums &＃61; [5,7,7,8,8,10], target &＃61; 8 输出: 2
示例 2:
输入: nums &＃61; [5,7,7,8,8,10], target &＃61; 6 输出: 0
提示&＃xff1a;

• 0 <&＃61; nums.length <&＃61; 105
• -109 <&＃61; nums[i] <&＃61; 109
• nums 是一个非递减数组
• -109 <&＃61; target <&＃61; 109

分析

一般这种题目在有序数组中查找一个数字都采用二分查找法。
需要记住以下模板套用&＃xff1a;
// 向下取整
int mid &＃61; (right - left) / 2 &＃43; left;
//向上取整
int mid &＃61; (right - left &＃43; 1) / 2 &＃43; left;
常⻅题型&＃xff1a;
1.寻找第⼀个⼤于等于 target 的数
2.寻找第⼀个等于 target 的数
3.寻找最后⼀个⼤于等于 target 的数
4.寻找最后⼀个等于 target 的数

//寻找第⼀个等于 target 的数的下标
int search2(int[] nums, int target){
if(nums &＃61;&＃61; null || nums.length <&＃61; 0){
return -1;
}
int left &＃61; 0, right &＃61; nums.length - 1;
while(left < right){
// 向下取整
int mid &＃61; (right - left) / 2 &＃43; left;
if(nums[mid] >&＃61; target){
right &＃61; mid;
}else{
left &＃61; mid &＃43; 1;
}
}
// 判断该数是否存在
if(nums[left] !&＃61; target) return -1;
return left;
}


//4.寻找最后⼀个等于 target 的数下标
int search4(int[] nums, int target){
if(nums &＃61;&＃61; null || nums.length <&＃61; 0){
return -1;
}
int left &＃61; 0, right &＃61; nums.length - 1;
while(left < right){
//向上取整
int mid &＃61; (right - left &＃43; 1) / 2 &＃43; left;
if(nums[mid] <&＃61; target){
left &＃61; mid;
}else{
right &＃61; mid - 1;
}
}
// 判断该数是否存在
if(nums[left] !&＃61; target) return -1;
return left;
}


代码

class Solution {
public int search(int[] nums, int target) {
int i &＃61; search2(nums,target);
int j &＃61; search4(nums,target);
if(j&＃61;&＃61;-1||i&＃61;&＃61;-1){
return 0;
}
return j-i&＃43;1;
}
int search2(int[] nums, int target){
if(nums &＃61;&＃61; null || nums.length <&＃61; 0){
return -1;
}
int left &＃61; 0, right &＃61; nums.length - 1;
while(left < right){
// 向下取整
int mid &＃61; (right - left) / 2 &＃43; left;
if(nums[mid] >&＃61; target){
right &＃61; mid;
}else{
left &＃61; mid &＃43; 1;
}
}
// 判断该数是否存在
if(nums[left] !&＃61; target) return -1;
return left;
}
//4.寻找最后⼀个等于 target 的数下标
int search4(int[] nums, int target){
if(nums &＃61;&＃61; null || nums.length <&＃61; 0){
return -1;
}
int left &＃61; 0, right &＃61; nums.length - 1;
while(left < right){
//向上取整
int mid &＃61; (right - left &＃43; 1) / 2 &＃43; left;
if(nums[mid] <&＃61; target){
left &＃61; mid;
}else{
right &＃61; mid - 1;
}
}
// 判断该数是否存在
if(nums[left] !&＃61; target) return -1;
return left;
}
}


一个长度为n-1的递增排序数组中的所有数字都是唯一的&＃xff0c;并且每个数字都在范围0&＃xff5e;n-1之内。在范围0&＃xff5e;n-1内的n个数字中有且只有一个数字不在该数组中&＃xff0c;请找出这个数字。

分析

这种有序的数组采用二分查找时间复杂度最低&＃xff0c;比较数组下标和数组值是否相等。

代码

class Solution {
public int missingNumber(int[] nums) {
int left &＃61; 0;
int right &＃61; nums.length-1;
while(left<right){
//向上取整
int mid &＃61; (right-left)/2&＃43;left;
if(nums[mid]&＃61;&＃61;mid){
left &＃61; mid&＃43;1;
}else{
right &＃61; mid;
}
}
return nums[left]&＃61;&＃61;left?left&＃43;1:left;
}
}