二分查找

  1. 算法简介
    二分查找也称折半查找(Binary Search),多数的人喜欢叫他二分查找。它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列,注意必须要是有序排列。

  2. 具体计算
    二分查找的基本思想是将n个元素分成大致相等的两部分,取a[n/2]与x做比较,如果x=a[n/2],则找到x,算法中止;如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.

704.二分查找

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

  1. 示例 1:

    1
    2
    3
    输入: nums = [-1,0,3,5,9,12], target = 9
    输出: 4
    解释: 9 出现在 nums 中并且下标为 4
  2. 示例 2:

    1
    2
    3
    输入: nums = [-1,0,3,5,9,12], target = 2
    输出: -1
    解释: 2 不存在 nums 中因此返回 -1
  • 提示:
    1. 你可以假设 nums 中的所有元素是不重复的。
    2. n 将在 [1, 10000]之间。
    3. nums 的每个元素都将在 [-9999, 9999]之间。

AC代码(704.二分查找)

1
2
3
4
5
6
7
8
9
10
11
12
var search = function(nums, target) {
let l = 0, r = nums.length - 1;
// 区间 [l, r]
while(l <= r) {
let mid = (l + r) >> 1;
if(nums[mid] === target) return mid;
let isSmall = nums[mid] < target;
l = isSmall ? mid + 1 : l;
r = isSmall ? r : mid - 1;
}
return -1;
};

line

278. 第一个错误的版本

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

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

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

  1. 示例 1:

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

    1
    2
    输入:n = 1, bad = 1
    输出:1
  • 提示:

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

AC代码(278. 第一个错误的版本)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int left=1;
int right=n;
while(left<right){
int mid=left+(right-left)/2;
if(isBadVersion(mid))
right=mid;
else
left=mid+1;
}
return left;
}
}

line

35. 搜索插入位置

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

请必须使用时间复杂度为 O(log n) 的算法。

  1. 示例 1:

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

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

    1
    2
    输入: nums = [1,3,5,6], target = 7
    输出: 4
  4. 示例 4:

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

    1
    2
    输入: nums = [1], target = 0
    输出: 0
  • 提示:

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

AC代码(35. 搜索插入位置)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int searchInsert(int[] nums, int target) {
int m=nums.length;
for(int i=0;i<m;i++) {
if(nums[i]==target) return i;
}
int i=0;
int j=m-1;
int mid=0;
while(i<j) {
mid=(j+i)/2;
if(nums[mid]>target) {
j=mid;
}else {
i=mid+1;
}
}
return nums[i]<target?i+1:i;
}
}