算法刷题记录-二分查找
二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
思路：low ,high表示代表当前查找范围，每次对比中间的值与target，相等则返回。若小于则将变为中间索引加+，否则为high为索引减一。Java实现如下
public int search(int[] nums, int target) {
int res=-1;
int low=0;int high=nums.length-1;
int mid=(low+high)/2;
while (low<=high){
if (nums[mid]==target){
res=mid;
break;
}
else if(nums[mid]<target){
low=mid+1;
mid=(low+high)/2;
}
else {
high=mid-1;
mid=(low+high)/2;
}
}
return res;
搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
思路：O(logn)就得用二分查找了，遇上一道题目类似。比较区间的中间位置与目标值。需要注意的是判断条件发生变化。
public int searchInsert(int[] nums, int target) {
int res=-1;
int low=0,high=nums.length-1;
int mid=(low+high)/2;
if (nums[0]>target){
res=0;
return res;
}
if (nums[high]<target){
res=high+1;
return res;
}
while ((high-low)>1){
if (nums[mid]==target){
return mid;
}
else if(nums[mid]<target){
low=mid;
mid=(low+high)/2;
}
else {
high=mid;
mid=(low+high)/2;
}
}
if (nums[low]==target){
res=low;
}
else if (nums[high]==target){
res=high;
}
else {
res = low + 1;
}
return res;
}
在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 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]
思路：这题相对复杂，需要考虑多种情况。不能按二分查找中间值实现，因为要返回的是一个区间。代码实现逻辑如下：
1.先初始化一些变量，low表示索引下限，high表示索引上限。flag值表示区间是否可能目标值。
2.进入循环前，先判断一些初始情况：数组为空，数组最大值小于查找值，数组最小值大于查找值。以及如果数组第一个或者最后一个与目标相同，直接将flag置true。
3.进入循环，当low和high的值不同时与target相同以及low小于target不结束循环。中间值比目标小，high=mid-1。反之low=mid+1，如果相同。看low与high哪个与target不同。不同的进行自加或者自减。
4.结束循环吗，如果flag为真，则复制。
public int[] searchRange(int[] nums, int target) {
int[] res=new int[2];
boolean flag=false;
res[0]=-1;res[1]=-1;
int low=0,high=nums.length-1;
int mid=(low+high)/2;
if (nums.length==0){
return res;
}
if (nums[0]> target){
return res;
}
if (nums[high]<target){
return res;
}
if (nums[low]==target & nums[high]==target){
flag=true;
}
while ((nums[low]!=target || nums[high]!=target)&(low<=high)){
if (nums[low]==target || nums[high]==target){
flag=true;
}
if (nums[mid]==target){
flag=true;
if (nums[low]!=target){
low=low+1;
}
if (nums[high]!=target){
high=high-1;
}
}
if (nums[mid]<target){
low=mid+1;
mid=(low+high)/2;
}
else if(nums[mid]>target){
high=mid-1;
mid=(low+high)/2;
}
}
if (flag){
res[0]=low;
res[1]=high;
}
return res;
}
有效的完全平方数
给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。
不能使用任何内置的库函数，如 sqrt 。
示例 1：
输入：num = 16
输出：true
解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。
示例 2：
输入：num = 14
输出：false
解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。
思路：1.暴力求解，没什么好说的，直接1到num/2一个一个判断。时间开销大（O(n)）
2.二分法：可以在1-num/2这个区间二分查找有没有满足条件的数。需要注意int精度不够，用long保存
代码如下：
public boolean isPerfectSquare(int num) {
boolean flag=false;
if(num==1){
flag=true;
}
int high=num/2;
int low=1;
int mid=(low+high)/2;
long data=(long) mid*mid;
while (low<=high){
if(data==num){
flag=true;
break;
}
else if(data<num){
low=mid+1;
mid=(low+high)/2;
data=(long) mid*mid;
}
else {
high=mid-1;
mid=(low+high)/2;
data=(long) mid*mid;
}
}
return flag;
}