Binary Search

喜欢ヅ旅行 2022-04-01 13:50 127阅读 0赞

简单的二分搜索：在一个非递减序整型数组中搜索值value，返回其所在下标  
最普通的二分搜索

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] Code   
 1 staticint BinarySearch(int\[\] arr, int value)  
 2 \{  
 3 int l =0;  
 4 int r = arr.Length \-1;  
 5   
 6 while (l <= r)  
 7  \{  
 8 // 防溢出，若使用 (l + r) / 2  
 9 // 当l 和 r 都很大时可能会溢出  
10 int m = l \+ (r \- l) /2;  
11   
12 if (arr\[m\] < value)  
13  l = m \+1;  
14 if (arr\[m\] == value)  
15 return m;  
16 if (arr\[m\] > value)  
17  r = m \-1;  
18  \}  
19   
20 return\-1;// 未找到  
21 \}  
22

有重复元素，返回下标最小的

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] Code   
 1 staticint BinarySearch2(int\[\] arr, int value)  
 2 \{  
 3 int l =0;  
 4 int r = arr.Length \-1;  
 5   
 6 while (l <= r)  
 7  \{  
 8 int m = l \+ (r \- l) /2;  
 9   
10 if (arr\[m\] < value)  
11  l = m \+1;  
12 if (arr\[m\] == value)  
13  \{  
14 // 如果左边有相等元素，且下标在范围内，继续比较  
15 if (m \-1>=0&& arr\[m \-1\] == value)  
16  r = m \-1;  
17 else//否则直接返回  
18 return m;  
19  \}  
20 if (arr\[m\] > value)  
21  r = m \-1;  
22  \}  
23   
24 return\-1;  
25 \}  
26

==

[ContractedBlock.gif]: https://www.cnblogs.com/Images/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220401/5627e7628deb45d4948e0cf827310089.png

发表评论取消回复

表情：

评论列表（有 0 条评论，127人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode（Binary Search Tree)108. Convert Sorted Array to Binary Search Tree

1.问题 Given an integer array nums where the elements are sorted in ascending order, co

左手的ㄟ右手/ 2023年09月26日 20:39/ 0 赞/ 78 阅读

相关 leetcode 95. Unique Binary Search Trees II | 96. Unique Binary Search Trees

95. Unique Binary Search Trees II [https://leetcode.com/problems/unique-binary-search

布满荆棘的人生/ 2022年09月10日 03:13/ 0 赞/ 122 阅读

相关 binary search（二分法）

binary search（二分法）：代码： import java.util.Arrays; / 二分法查找元素 /

叁歲伎倆/ 2022年09月04日 11:59/ 0 赞/ 106 阅读

相关二分查找（binary search）

二分查找:又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。实例代码： //binary search arra

迈不过友情╰/ 2022年08月20日 13:10/ 0 赞/ 116 阅读

相关 11. Search Range in Binary Search Tree

11. Search Range in Binary Search Tree Description Given two values k1 and k2

分手后的思念是犯贱/ 2022年05月27日 08:39/ 0 赞/ 142 阅读

相关 Algorithm - Binary Search（Java）

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击[http://www.captainbed.net][http_www.cap

你的名字/ 2022年05月24日 06:20/ 0 赞/ 90 阅读

相关 [C++][STL] binary_search

所需的页眉 <algorithm> 回到顶端原型 template<class ForwardIterator,

比眉伴天荒/ 2022年04月11日 05:28/ 0 赞/ 104 阅读

相关 Binary Search

简单的二分搜索：在一个非递减序整型数组中搜索值value，返回其所在下标最普通的二分搜索 ![ContractedBlock.gif][] ![ExpandedBloc

喜欢ヅ旅行/ 2022年04月01日 13:50/ 0 赞/ 128 阅读

相关 Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST

刺骨的言语ヽ痛彻心扉/ 2021年12月17日 10:35/ 0 赞/ 174 阅读

相关 Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1...

刺骨的言语ヽ痛彻心扉/ 2021年12月17日 10:29/ 0 赞/ 184 阅读