二分查找【数组】

二分查找
704
实现思路：
1.定义两个指针分别指向数组的开始索引和最后索引；
while循环
2.mid = left + ((right - left) >> 1);
判断
如果 target < nums[mid]
right = mid - 1
如果 target > nums[mid]
left = mid + 1
如果 target == nums[mid]
return mid

否则循环结束 return -1

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left <= right) {
            int mid = left + ((right - left) >> 1);// mid需要放在循环内更新
            if (target < nums[mid]) {
                right =  mid - 1;
            } else if (target > nums[mid]) {
                left = mid + 1;
            } else if (target == nums[mid]) {
                return mid;
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

class Solution {
    public int searchInsert(int[] nums, int target) {
        /*实现思路
        1 遍历数组× --> 二分查找，如果在数组中，返回其索引
        2 如果数组中没有该元素， 由于target > nums[i], 跳出wihle循环时，双指针的left指针一致指向mid + 1，最终会指向索引的最大位置后面的那个索引
        */
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (target == nums[mid]) {
                return mid;
            } else if (target > nums[mid]) {
                left = mid + 1;
            } else { 
                 right = mid - 1;
            }
        }
        return left;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

36. 在排序数组中查找元素的第一个和最后一个位置
    给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
    如果数组中不存在目标值 target，返回 [-1, -1]。
    你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

class Solution {
    /*
    实现思路，用两个双指针分别搜索目标元素target的开始索引和结束索引；存入 new int[] {start, end} 返回
    需要注意处理细节，如搜索开始索引时，单独定义一个私有方法。找到了res == mid 的时候，不要直接返回，而是将mid - 1的位置传递给 right指针，继续在它的左区间去搜索，找到另一个目标元素，如此循环直到找到最左边的目标元素的索引作为返回结果； 最大索引思路与此一致。
    */
    public int[] searchRange(int[] nums, int target) {
        int start = findStart(nums, target);
        int end = findEnd(nums, target);
        return new int[]{start, end};
    }

    private int findStart (int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1; 
        int res = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2; //【需要注意】mid的更新在while循环内部，而初始化在while循环的外面
            if (target == nums[mid]) {
                res = mid;
                right = mid - 1; //与另一个私有方法findEnd只有这里不同！
            } else if (target > nums[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return res;
    }

    private int findEnd (int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1; 
        int res = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (target == nums[mid]) {
                res = mid;
                left = mid + 1;
            } else if (target > nums[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return res;
    }
}
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
36
37
38
39
40
41
42
43
44
45
46
47