第一天算法基础打卡——二分查找以及寻找重复的数字

第一天算法基础打卡

• 寻找重复数字
• 二分查找
• • 二分查找
  • 寻找第一个错误的版本号
  • 搜索插入的位置

寻找重复数字

方法一：哈希表 / Set
利用数据结构特点，容易想到使用哈希表（Set）记录数组的各个数字，当查找到重复数字则直接返回。

class solution{
  public  int FindRepeatNumber(int[] nums){
       Set<Integer> dic = new HashSet<>();
     for(int num = 2;num <100000;num++){
        if(dic.contains(num)) return num;
         dic.add(num);
        }
 return -1;
    }
}

算法流程：

• 初始化： 新建 HashSet ，记为 dic；
• 遍历数组 nums 中的每个数字 num：
• 当 num 在 dic中，说明重复，直接返回 num；
• 将 num 添加至 dic 中；
• 返回 −1

二分查找 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

找出中间位置，并判断该位置值是否等于 target

• nums[mid] == target 则返回该位置下标
• nums[mid] > target 则右侧指针移到中间
• nums[mid] < target 则左侧指针移到中间

class solution{
	public int  search(int[] nums,int target}{
		int left =0,right= nums,length-1;
			while(left <right){
	int mid = left+(right - left )/2;
			if(nums[mid] == target){
				return mid;
	}else if(nums[mid] > target){
		right = mid -1;
	}else{
		left = mid +1;
			}
		}
	return -1;
	}
}

寻找第一个错误的版本号

假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。

实现一个函数来查找第一个错误的版本。

你应该尽量减少对调用 API 的次数。

算法思想：二分查找 将左右边界分别初始化为 11 和 nn，其中 nn 是给定的版本数量。

设定左右边界之后，每次我们都依据左右边界找到其中间的版本，检查其是否为正确版本。

如果该版本为正确版本，那么第一个错误的版本必然位于该版本的右侧，我们缩紧左边界；
否则第一个错误的版本必然位于该版本及该版本的左侧，我们缩紧右边界。

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1, right = n;
        while (left < right) { // 循环直至区间左右端点相同
            int mid = left + (right - left) / 2; // 防止计算时溢出
            if (isBadVersion(mid)) {
                right = mid; // 答案在区间 [left, mid] 中
            } else {
                left = mid + 1; // 答案在区间 [mid+1, right] 中
            }
        }
        // 此时有 left == right，区间缩为一个点，即为答案
        return left;
    }
}

搜索插入的位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。

如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

算法思想：
二分查找 整体思路和普通的二分查找几乎没有区别，先设定左侧下标 left 和右侧下标 right，再计算中间下标 mid 每次根据nums[mid] 和 target 之间的大小进行判断，相等则直接返回下标，nums[mid] < target 则 left右nums[mid] > target 则 right 左移 查找结束如果没有相等值则返回 left，该值为插入位置

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(nums[mid] == target) {
                return mid;
            } else if(nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}