【14天算法入门】-第1天-二分查找

桃扇骨 2022-09-12 10:47 156阅读 0赞

**目录**

1、经典二分查找

2、返回错误的版本

3、搜索插入位置

--------------------

# 1、经典二分查找 #

/\*\*  
 \* 704. 二分查找  
 \*给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。  
 \*输入: nums = \[-1,0,3,5,9,12\], target = 9  
 \* 输出: 4  
 \* 解释: 9 出现在 nums 中并且下标为 4  
 \* \*/

public class searchHalf {
    
        public int search(int[] nums, int target) {
            int i=0;
            int j=nums.length-1;
    
            while(i<=j){
                if((target < nums[i]) || (target > nums[j])){
                    return -1;
                }
                int mid = i+(j-i)/2;
                if(target < nums[mid]){
                    j = mid-1;
                }else if (target > nums[mid]){
                    i = mid+1;
                }else{
                    return mid;
                }
            }
    
            return -1;
        }
    }

# 2、返回错误的版本 #

/\*\*  
 \* 278. 第一个错误的版本  
 \*你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。  
 \*  
 \* 假设你有 n 个版本 \[1, 2, ..., n\]，你想找出导致之后所有版本出错的第一个错误的版本。  
 \* 你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。  
 \* \*/

public class firstBadVersion {
        //二分查找的变体, 当天false，后一个true
        public int firstBadVersion(int n) {
    
            int i = 1;
            int j = n;
    
            if(isBadVersion(1)){
                return 1;
            }
    
            while(i<=j){
                int mid = i + (j-i)/2;
                if(!isBadVersion(mid)){//mid版本正确
                    if(isBadVersion(mid+1)){//mid+1版本错误
                        return mid+1;
                    }else{//mid+1版本正常
                        i = mid+1;
                    }
                }else{//mid版本错误
                    if(!isBadVersion(mid-1)){//mid-1版本正确
                        return mid;
                    }else{//mid-1版本正确
                        j = mid-1;
                    }
                }
            }
            return -1;
        }
    
        boolean isBadVersion(int version);
    }

# 3、搜索插入位置 #

/\*\*  
 \* 35. 搜索插入位置  
 \* 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。  
 \* 请必须使用时间复杂度为 O(log n) 的算法。  
 \* \*/

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