hello-algo/codes/ruby/chapter_searching/binary_search_edge.rb
bluebean-cloud 92337671a6
feat: Add Ruby code - chapter "Searching" (#1262)
* create RUBY searching files & finish two_sum.rb

* finish linear_search.rb

* finish hashing_search.rb

* finish binary_search.rb

* finish binary_search_insertion.rb

* finish binary_search_edge.rb

* fix: change 'or' to '||'

* fix: Adjust the code style(ruby searching)

* fix: repair file name

* fix: Adjust the output format

* fix: fix 0...nums.length & delete useless require & change into __FILE__==0 block
2024-04-12 03:10:15 +08:00

47 lines
1.2 KiB
Ruby
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.

=begin
File: binary_search_edge.rb
Created Time: 2024-04-09
Author: Blue Bean (lonnnnnnner@gmail.com)
=end
require_relative './binary_search_insertion'
### 二分查找最左一个 target ###
def binary_search_left_edge(nums, target)
# 等价于查找 target 的插入点
i = binary_search_insertion(nums, target)
# 未找到 target ,返回 -1
return -1 if i == nums.length || nums[i] != target
i # 找到 target ,返回索引 i
end
### 二分查找最右一个 target ###
def binary_search_right_edge(nums, target)
# 转化为查找最左一个 target + 1
i = binary_search_insertion(nums, target + 1)
# j 指向最右一个 target i 指向首个大于 target 的元素
j = i - 1
# 未找到 target ,返回 -1
return -1 if j == -1 || nums[j] != target
j # 找到 target ,返回索引 j
end
### Driver Code ###
if __FILE__ == $0
# 包含重复元素的数组
nums = [1, 3, 6, 6, 6, 6, 6, 10, 12, 15]
puts "\n数组 nums = #{nums}"
# 二分查找左边界和右边界
for target in [6, 7]
index = binary_search_left_edge(nums, target)
puts "最左一个元素 #{target} 的索引为 #{index}"
index = binary_search_right_edge(nums, target)
puts "最右一个元素 #{target} 的索引为 #{index}"
end
end