小白的悟道
0%

Binary Search

发表于 分类于 Valine：

二分查找通常将待查找区间分为两部分并只取一部分继续查找，可以大大减少查找的复杂度。

求开方

  1. Sqrt(x) (Easy)

题目描述

　　给定一个非负整数，求它的开方，向下取整。

输入输出样例

　　输入是一个整数，输出一个整数。

1
2
Input: 8
Output: 2

c++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int mySqrt(int a) {
    if (a == 0) return 0;
    int l = 1, r = a, mid, sqrt;
    while (l <= r) {
        mid = l + (r - 1) / 2;
        sqrt = a / mid;
        if (sqrt == mid) {
            return mid;
        } else if (mid > sqrt) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return r;
}

java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//注意int强转long的用法
class Solution {
    public int mySqrt(int x) {
        int l = 0;
        int r = x;
        int ans = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if ((long)mid * mid <= x) {
                l = mid + 1;
                ans = mid;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
}

查找区间

  1. Find First and Last Position of Element in Sorted Array (Medium)

题目描述

　　给定一个增序的整数数组和一个值，查找该值第一次和最后一次出现的位置。

输入输出样例

　　输入是一个数组和一个值，输出为该值第一次出现的位置和最后一次出现的位置(从0开始);如果不存在该值，则两个返回值都设为-1。

1
2
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3, 4]

c++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
vector<int> searchRange(vector<int>& nums, int target) {
    if (nums.empty()) return vector<int>{-1, -1};
    int lower = lower_bound(nums, target);
    int upper = upper_bound(nums, target) - 1;
    if (lower == nums.size() ## nums[lower] != target) {
        retrun vector<int>{-1, -1};
    }
}

int lower_bound(vector<int>& nums, int target) {
    int l = 0, r = nums.size(), mid;
    while (l < r) {
        mid = (l + r) / 2;
        if (nums[mid] >= target) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

int upper_bound(vector<int>& nums, int target) {
    int l = 0, r = nums.size(), mid;
    while (l < r) {
        mid = (l + r) / 2;
        if (nums[mid] > target) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//拆解为两个二分查找，注意收敛边界
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = binarySearch(nums, target, true);
        int right = binarySearch(nums, target, false);
        return new int[]{left, right};
    }

    public int binarySearch(int[] nums, int target, Boolean leftFlag) {
        int result = -1;
        if (nums.length <= 0) {
            return result;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target && leftFlag && (0 == mid || nums[mid - 1] < nums[mid])) {
                return mid;
            } else if (nums[mid] == target && !leftFlag && (mid == nums.length - 1 || nums[mid + 1] > nums[mid])) {
                return mid;
            } else if ((leftFlag && nums[mid] >= target) || (!leftFlag && nums[mid] > target)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }
}

旋转数组查找数字

  1. Search in Rotated Sorted Array (Medium)

题目描述

　　一个原本增序的数组被首尾相连后按某个位置断开（如[1,2,2,3,4,5]->[2,3,4,5,1,2],在第一位和第二位断开），我们称其为旋转数组。给定一个值，判断这个值是否存在于这个为旋转数组中。

输入输出样例

　　输入是一个数组和一个值，输出是一个布尔值，表示数组中是否存在于这个旋转数组中。

1
2
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

c++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
bool search(vector<int>& nums, int target) {
    int start = 0, end = nums.size() - 1;
    while (start < end) {
        mid = (start + end) / 2;
        if (nums[mid] == target) {
            return true;
        }
        if (nums[start] == nums[mid]) {
            ++start;
        } else if (nums[mid] <= nums[end]) {
            if (target > nums[mid] && target <= nums[end]) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        } else {
            if (target >= nums[start] && target < nums[mid]) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
    }
    return flase;
}

java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//注意区分有序空间
class Solution {
    public boolean search(int[] nums, int target) {
//        nums = [2,5,6,0,0,1,2]
        int left = 0;
        int right = nums.length - 1;
        boolean res = false;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return true;
            } else if (nums[left] < nums[mid]) { //在前面升区间上
                if (nums[mid] < target) {
                    left = mid + 1;//一定对的，因为它右边的大
                } else if (nums[left] > target) {//左边的最小值的大于它，可能在右边
                    left = mid + 1;
                } else {//否则一定在左边
                    right = mid - 1;
                }
            } else if (nums[left] > nums[mid]) {
//                nums = [2,5,6,0,0,1,2]
                if (nums[mid] > target) { //在后面升区间上
                    right = mid - 1;//一定对的，小的在左边
                } else if (nums[right] < target) {
                    right = mid - 1;//最右边的最大值还没达到最大值，在左边
                } else {
                    left = mid + 1;
                }
            } else {
                left++;
            }
        }
        return res;
    }
}