二分查找算法实现

发表于 更新于 分类于 阅读次数：
本篇文章使用Lua语言实现二分查找算法。

二分查找（非递归实现）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
-- 二分查找（BinarySearch）非递归实现
-- 空间复杂度为O（1）
-- 时间复杂度：平均情况O(logn)
function binarySearch(array, value)
	local low = 1
	local high = #array
	while(low<=high) do
		local mid = math.floor((high+low)/2)
		if array[mid] < value then
			low = mid + 1
		elseif array[mid] > value then
			high = mid - 1
		else
			return mid
		end
	end
	return -1
end

二分查找（递归实现）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
-- 二分查找（BinarySearch）递归实现
function binarySearch1(array, value, low, high)
	if low > high then
		return -1
	end 

	local mid = math.floor((high+low)/2)
	if array[mid] > value then
		return binarySearch1(array, value, low, high-1)
	elseif array[mid] < value then
		return binarySearch1(array, value, low+1, high)
	else
		return mid
	end
end

查找第一个值等于给定值的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
--查找第一个值等于给定值的元素
function bsearchFirstValue(array, value)
	local low = 1
	local high = #array

	while(low<=high) do
		local mid = math.floor((high+low)/2)
		if array[mid] > value then
			high = mid - 1
		elseif array[mid] < value then
			low = mid + 1
		else
			if mid==1 or array[mid-1]~=value then
				return mid
			else
				high = mid - 1
			end
		end
	end

	return -1
end

–查找最后一个值等于给定值的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
--查找最后一个值等于给定值的元素
function bsearchLastValue(array, value)
	local low = 1
	local high = #array

	while(low<=high) do
		local mid = math.floor((high+low)/2)
		if array[mid] > value then
			high = mid - 1
		elseif array[mid] < value then
			low = mid + 1
		else
			if mid==#array or array[mid+1]~=value then
				return mid
			else
				low = mid + 1
			end
		end
	end

	return -1
end

查找第一个值大于等于给定值的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
--查找第一个值大于等于给定值的元素
function bsearchGeValue(array, value)
	local low = 1
	local high = #array

	while(low<=high) do
		local mid = math.floor((high+low)/2)
		if array[mid] >= value then
			if mid==1 or array[mid-1]<value then
				return mid
			else
				high = mid - 1
			end
		else
			low = mid + 1
		end
	end

	return -1
end

查找最后一个值小于等于给定值的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
--查找最后一个值小于等于给定值的元素
function bsearchLeValue(array, value)
	local low = 1
	local high = #array

	while(low<=high) do
		local mid = math.floor((high+low)/2)
		if array[mid] <= value then
			if mid==#array or array[mid+1]>value then
				return mid
			else
				low = mid + 1
			end
		else
			high = mid - 1
		end
	end

	return -1
end

Test

1
2
3
4
5
6
7
8
9
-- local t = {2, 4, 5, 7, 9}
-- print(binarySearch(t, 5))
-- print(binarySearch1(t, 1, 1, #t))

local t1 = {2, 2, 4, 5, 5, 5, 7, 9}
-- print(bsearchFirstValue(t1, 0))
-- print(bsearchLastValue(t1, 1))
-- print(bsearchGeValue(t1, 10))
print(bsearchLeValue(t1, 5))