经典算法之二分查找（Python，Shell与Java实现）
1、算法思想
二分查找采用分而治之的思想。 要求被查找的集合必须是有序的。 主要思路：
- 根据起始位置和结束位置，确定中间位置。
- 拿目标值与中间位置的值做比较，假如目标值大于中间位置取值，则起始位置为中间位置加1。
- 假如目标值小于中间位置取值，则结束位置为中间位置减1。
- 直至起始位置小于等于结束位置，找到目标值的位置即索引。
2、代码实现
2.1、基于Python3.x实现
代码如下：
#coding:utf-8
def half_search(lst,key):
start = 0
end = len(lst) - 1
while start <= end:
mid = int(start + end / 2)
if lst[mid] > key:
end = mid - 1
elif lst[mid] < key:
start = mid + 1
else:
print("Matched the index of key %s is %s" %(lst[mid],mid))
return mid
return -1
l=[1,2,3,5,7]
half_search(l,2)
运行结果：
Matched the index of key 2 is 1
2.2、基于shell实现
代码如下：
#/bin/bash
function BinSearch(){
declare -a arr=($1)
key=$2
start=0
end=`expr ${#arr[*]} - 1`
while [ ${start} -le ${end} ]
do
declare -i mid=$(((start+end)/2))
if [ ${arr[mid]} -lt ${key} ];then
start=$((mid+1))
elif [ ${arr[mid]} -gt ${key} ];then
end=$((mid-1))
else
echo ${mid}
break
fi
done
}
arr=(1 2 3 5 7 9)
echo "Index of 2 is:$(BinSearch "${arr[*]}" 2)"
运行结果：
Index of 2 is:1
2.3、基于Java实现
代码如下：
class binSearch{
//定义二分查找的函数
public static int binSearch(int[] arr,int key){
int start=0;
int end=arr.length - 1;
//int mid=(start+end) /2;
while(start<=end){
int mid = (start + end) / 2;
if(arr[mid]<key){
start=mid+1;
}
else if(arr[mid]>key){
end=mid-1;
}
else{
System.out.print("Matched,index is:");
return mid;
}
}
return -1;
}
//验证二分查找
public static void main(String[] args){
int key=2;
int[] arr={1,2,3,5,7,9};
int keyIndex=binSearch(arr,key);
System.out.print(keyIndex);
}
}
运行结果：
Matched,index is:1
Linux公社的RSS地址 ： https://www.linuxidc.com/rssFeed.aspx
本文永久更新链接地址： https://www.linuxidc.com/Linux/2019-04/158113.htm
正文到此结束
热门推荐
相关文章
近期评论
-
666
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
