hello-algo/codes/csharp/chapter_searching/binary_search_edge.cs
hpstory 56b20eff36
feat(csharp) .NET 8.0 code migration (#966)
* .net 8.0 migration

* update docs

* revert change

* revert change and update appendix docs

* remove static

* Update binary_search_insertion.cs

* Update binary_search_insertion.cs

* Update binary_search_edge.cs

* Update binary_search_insertion.cs

* Update binary_search_edge.cs

---------

Co-authored-by: Yudong Jin <krahets@163.com>
2023-11-26 23:18:44 +08:00

50 lines
1.7 KiB
C#
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

/**
* File: binary_search_edge.cs
* Created Time: 2023-08-06
* Author: hpstory (hpstory1024@163.com)
*/
namespace hello_algo.chapter_searching;
public class binary_search_edge {
/* 二分查找最左一个 target */
int BinarySearchLeftEdge(int[] nums, int target) {
// 等价于查找 target 的插入点
int i = binary_search_insertion.BinarySearchInsertion(nums, target);
// 未找到 target ,返回 -1
if (i == nums.Length || nums[i] != target) {
return -1;
}
// 找到 target ,返回索引 i
return i;
}
/* 二分查找最右一个 target */
int BinarySearchRightEdge(int[] nums, int target) {
// 转化为查找最左一个 target + 1
int i = binary_search_insertion.BinarySearchInsertion(nums, target + 1);
// j 指向最右一个 target i 指向首个大于 target 的元素
int j = i - 1;
// 未找到 target ,返回 -1
if (j == -1 || nums[j] != target) {
return -1;
}
// 找到 target ,返回索引 j
return j;
}
[Test]
public void Test() {
// 包含重复元素的数组
int[] nums = [1, 3, 6, 6, 6, 6, 6, 10, 12, 15];
Console.WriteLine("\n数组 nums = " + nums.PrintList());
// 二分查找左边界和右边界
foreach (int target in new int[] { 6, 7 }) {
int index = BinarySearchLeftEdge(nums, target);
Console.WriteLine("最左一个元素 " + target + " 的索引为 " + index);
index = BinarySearchRightEdge(nums, target);
Console.WriteLine("最右一个元素 " + target + " 的索引为 " + index);
}
}
}