704.二分查找
- 思路：二分查找的前置条件是数组有序且无重复元素，每次通过改变边界值来缩小查找范围。
自己写的:
可以看到对边界的判断存在问题，基本思路是左闭右闭，但是while循环的判断是按照左闭右开来写的。对于数组中仅包含一个元素且该元素是目标函数的情况会出错。重新调试后添加了一个low==high的判断，实际上可以整合到while循环里。
public int search(int[] nums, int target) {
int low = 0, high = nums.length - 1, mid = (low + high) / 2;
while (low < high){
int temp = nums[mid];
if(temp == target){
return mid;
}else{
if(temp > target){
high = mid - 1;
}else{
low = mid + 1;
}
mid = (low + high) / 2;
}
}
//对于nums=[5]且target=5的情况重新进行边界分析后添加的判断
if(low == high && nums[low] == target){
return low;
}
return -1;
}
左闭右闭
public int search(int[] nums, int target) {
int low =0, high = nums.length - 1; //定义target在左闭右闭区间[low,high]里
while(low <= high){ //取等号，因为low==high的情况是合法的
int mid = low + ((high - low) / 2); //这种写法可以避免两个int型相加溢出
if(nums[mid] == target){ //找到target,返回下标mid
return mid;
}else if(nums[mid] < target){ //tareget在右半区间，low右移
low = mid + 1;
}else if(nums[mid] > target){ //target在左半区间，high左移
high = mid - 1;
}
}
return -1;
}
左闭右开
public int search(int[] nums, int target) {
int low = 0, high = nums.length; //定义target在左闭右开区间[low,high)中，右边界是不取的，所以high不用-1
while(low < high){ //对于左开右闭区间，low==high不合法
int mid = low + ((high - low) / 2);
if(nums[mid] == target){
return mid;
}else if(nums[mid] < target){ //target在右半部分，右移low，由于区间左闭，故low=mid+1
low = mid + 1;
}else if(nums[mid] > target){ //target在左半部分，左移high,由于区间右开，故high=mid
high = mid;
}
}
return -1;
}
相关问题
35.搜索插入位置
自己写的
public int searchInsert(int[] nums, int target) {
int low = 0, high = nums.length - 1;
while(low <= high){
int mid = low + ((high - low) / 2);
if(nums[mid] == target){
return mid;
}else if(nums[mid] < target){
low = mid + 1;
}else if(nums[mid] > target){
high = mid - 1;
}
}
return low;
}
34.在排序数组中查找元素的第一个和最后一个位置
自己写的
二分法找到第数组中第一个target后，向两边扫描找到边界。
public int[] searchRange(int[] nums, int target) {
int low = 0, high = nums.length - 1;
//用于储存始末下标
int[] locas = new int[]{-1,-1};
while(low <= high){
int mid = low + ((high - low) / 2);
if(nums[mid] == target){
locas[0] = mid;
locas[1] = mid;
int left = mid - 1, right = mid + 1;
//向左边搜索第一个目标元素
while(left >= 0 && nums[left] == target){
locas[0] = left;
left--;
}
//向右边搜索最后一个目标元素
while(right < nums.length && nums[right] == target){
locas[1] = right;
right++;
}
break;
}else if(nums[mid] < target){
low = mid + 1;
}else if(nums[mid] > target){
high = mid - 1;
}
}
return locas;
}
使用二分法分别探索边界
存在三种情况
- target的值不在nums区间内
- target的值在nums区间内但不是nums的元素
- target的值在nums区间内且是nums的元素
探索左边界，即寻找下标最小的与target值相等的元素
探索右边界，即寻找下标最大的与target值相等的元素
27. 移除元素
自己写的：
遍历数组，如果当前元素与val值相等，就用最后一个元素覆盖它并减小数组长度，并再次检查是否覆盖后的值依旧与val相等
public int removeElement(int[] nums, int val) {
int len = nums.length; //记录数组长度
for(int i = 0;i < len;i++){
if(nums[i] == val){ //如果当前元素值等于val，用数组最后一个值覆盖并减小数组的长度
nums[i] = nums[len - 1];
len--;
i--; //存在数组最后一个值也是val的可能，再次检查
}
}
return len;
}
暴力法
用两个for循环，当第一个循环找到与val值相等的元素时，通过第二个循环将元素整体前移并减小数组长度
public int removeElement(int[] nums, int val) {
int len =nums.length;
for(int i = 0;i < len;i++){
if(nums[i] == val){
for(int j = i + 1;j < len;j++){
nums[j - 1] = nums[j];
}
len--;
i--;
}
}
return len;
}
快慢指针
快指针扫描旧数组，慢指针标记新数组下标。
当快指针扫描到的元素不等于val时赋给慢指针标记的位置并更新慢指针;
若快指针扫到的元素等于val时，只更新快指针，跳过该元素
public int removeElement(int[] nums, int val) {
int slow = 0;
for(int fast = 0; fast < nums.length; fast++){
if(nums[fast] != val){
nums[slow] = nums[fast];
slow ++;
}
}
return slow;
}