LeetCode:Search Insert Position,Search for a Range (二分查找,lower_bound,upper_bound)

简介:

Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples. 
[1,3,5,6], 5 → 2 
[1,3,5,6], 2 → 1 
[1,3,5,6], 7 → 4 
[1,3,5,6], 0 → 0

 

这就是普通的二分查找,需要注意的地方代码注释中都有。其中特别注意的是:middle=(low+high)/ 2 ,可能会溢出,可以替换为middle = low + ((high - low)>>2);

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class  Solution {
public :
     int  searchInsert( int  A[], int  n, int  target) {
         //二分查找
         int  low = 0, high = n-1; //注意这里high是初始化为n-1
         while (low <= high) //注意这里是<=号
         {
             //int middle = (low + high) / 2;
             int  middle = low + ((high - low)>>2); //可以防止low + high 溢出
             if (A[middle] < target)
                 low = middle + 1;
             else  if (A[middle] > target)
                 high = middle - 1;
             else  return  middle;
         }
         return  low; //注意返回值是low
     }
};

 

根据程序员编程艺术第二十五章:Jon Bentley:90%无法正确实现二分查找, 如果high初始化为n, 那么while判断语句就应该是low<high, 下面的A[middle] > target分支中,就应该是high = middle

 


Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example, 
Given [5, 7, 7, 8, 8, 10] and target value 8, 
return [3, 4].

 

看到这个有没有想到STL中的equal_range函数,这个函数是调用lower_boundupper_bound, 下面我们仿照STL的实现。相比上一题的二分查找,lower_bound当A[middle] == target时,继续向左半部分查找,它返回的是第一个不小于目标数的元素位置;upper_bound当A[middle] == target时,继续向右半部分查找,它返回的是第一个大于目标数的元素位置。    本文地址

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
48
49
class  Solution {
public :
     vector< int > searchRange( int  A[], int  n, int  target) {
         vector< int > res(2, -1);
         int  low = 0, high = n-1;
         while (low <= high)
         {
             int  middle = low + ((high - low)>>2);
             if (A[middle] < target)
                 low = middle + 1;
             else  if (A[middle] > target)
                 high = middle - 1;
             else
             {
                 res[0] = lowerBound(A, low, middle - 1, target);
                 res[1] = upperBound(A, middle + 1, high, target) - 1;
                 return  res;
             }
         }
         return  res;
     }
     
     //找到范围内[left,right]内第一个不小于target的元素
     int  lowerBound( int  A[], int  left, int  right, int  target)
     {
         int  low = left, high = right;
         while (low <= high)
         {
             int  middle = low + ((high - low)>>2);
             if (A[middle] < target)
                 low = middle + 1;
             else  high = middle - 1;
         }
         return  high + 1; //注意这里返回值不是low
     }
     //找到范围[left,right]内第一个大于target的元素
     int  upperBound( int  A[], int  left, int  right, int  target)
     {
         int  low = left, high = right;
         while (low <= high)
         {
             int  middle = low + ((high - low)>>2);
             if (A[middle] <= target)
                 low = middle + 1;
             else  high = middle - 1;
         }
         return  low;
     }
};





本文转自tenos博客园博客,原文链接:http://www.cnblogs.com/TenosDoIt/p/3681677.html,如需转载请自行联系原作者

目录
相关文章
|
6月前
leetcode:374. 猜数字大小(二分查找)
leetcode:374. 猜数字大小(二分查找)
36 0
|
6月前
|
算法 测试技术 C#
【二分查找】【区间合并】LeetCode2589:完成所有任务的最少时间
【二分查找】【区间合并】LeetCode2589:完成所有任务的最少时间
|
1月前
【LeetCode 01】二分查找总结
【LeetCode 01】二分查找总结
14 0
|
3月前
|
Python
【Leetcode刷题Python】704. 二分查找
解决LeetCode "二分查找" 问题的Python实现代码。
18 0
|
3月前
|
算法 索引 Python
【Leetcode刷题Python】34. 在排序数组中查找元素的第一个和最后一个位置(二分查找)
解决LeetCode "在排序数组中查找元素的第一个和最后一个位置" 问题的方法。第一种方法是使用两次二分查找,首先找到目标值的最左边界,然后找到最右边界。第二种方法是利用Python的list.index()方法,先正序找到起始位置,再逆序找到结束位置,并给出了两种方法的Python实现代码。
61 0
|
5月前
|
索引
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
|
5月前
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板
|
5月前
|
算法 数据可视化 数据挖掘
深入解析力扣162题:寻找峰值(线性扫描与二分查找详解)
深入解析力扣162题:寻找峰值(线性扫描与二分查找详解)
|
6月前
|
算法 索引
【数据结构与算法 | 基础篇】力扣704/35/34:二分查找
【数据结构与算法 | 基础篇】力扣704/35/34:二分查找
|
5月前
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名