二分查找

「算法」 – 学习计划 – 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-cn.com)

跟着这个leecode的计划复习下这些算法

704. 二分查找

难度 简单

给定一个 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

提示：

1. 你可以假设 nums 中的所有元素是不重复的。
2. n 将在 [1, 10000]之间。
3. nums 的每个元素都将在 [-9999, 9999]之间。

public class Question704 {
	public static int search(int[] nums, int target) {
		int low = 0; int high = nums.length - 1;
		while (low<=high){
			int mid = (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 -1;
	}


	public static void main(String args[]){
		System.out.println(search(new int[]{-1,0,3,5,9,12}, -1));
		System.out.println(search(new int[]{-1,0,3,5,9,12}, 9));
		System.out.println(search(new int[]{-1,0,3,5,9,12}, 2));
	}



}

704题是一个基础版本，返回的是下标，定时low和high用的是[0,n-1], 循环时候是<=判断

278. 第一个错误的版本

/**

 你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

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

 你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。


 示例 1：

 输入：n = 5, bad = 4
 输出：4
 解释：
 调用 isBadVersion(3) -> false
 调用 isBadVersion(5) -> true
 调用 isBadVersion(4) -> true
 所以，4 是第一个错误的版本。
 示例 2：

 输入：n = 1, bad = 1
 输出：1


 提示：

 1 <= bad <= n <= 231 - 1


 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/first-bad-version
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 * @author zeroheart
 *
 */



public class Question278 {
	public int firstBadVersion(int n) {
		int low = 0;
		int high = n-1;

		while (low <= high){
			// 防止溢出
			int mid = low + (high - low) / 2;
			//int mid = (high+low) / 2;
			if(isBadVersion(mid)){
				high = mid - 1;
			}else {
				low = mid + 1;
			}
		}
		return low;
	}

}

278题是变种，返回的是第几个元素，最终输出low，同时，为了防止溢出，mid的算法改为int mid = low + (high – low) / 2

35. 搜索插入位置

/**
 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

 请必须使用时间复杂度为 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
 示例 4:

 输入: nums = [1,3,5,6], target = 0
 输出: 0
 示例 5:

 输入: nums = [1], target = 0
 输出: 0


 提示:

 1 <= nums.length <= 10^4
 -10^4 <= nums[i] <= 10^4
 nums 为无重复元素的升序排列数组
 -10^4 <= target <= 10^4

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/search-insert-position
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 * @author zeroheart
 *
 */
public class Question35 {
    public static int searchInsert(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;

        while (low <= high){
            int mid = low + (high - low) / 2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid]>target) {
                high = mid - 1;
            }else {
                low = mid + 1;
            }
        }
        // 寻找插入的位置，所有都和基础二分一样，只有这里在所有都无法匹配之后,
        // 因为退出时候，low和high的情况一定是以下情况
        // 目标值在数组所有元素之前  [0, -1]
        // 目标值等于数组中某一个元素  return middle;
        // 目标值插入数组中的位置 [low, high]
        // 目标值在数组所有元素之后的情况 [n+1, n]
        // 所以，最后返回 high + 1 或者返回 low
        return high + 1;
    }

    public static void main(String args[]){
        System.out.println(searchInsert(new int[]{-1,0,3,5,9,12}, -2));
        System.out.println(searchInsert(new int[]{-1,0,3,5,9,12}, -1));
        System.out.println(searchInsert(new int[]{-1,0,3,5,9,12}, 9));
        System.out.println(searchInsert(new int[]{-1,0,3,5,9,12}, 2));
    }

}

35题主要是找一个插入的位置，使用二分法的话，和普通二分的区别就在最后一行返回值的位置，return high + 1;