二分查找采用分而治之的思想。要求被查找的集合必须是有序的。主要思路：
根据起始位置和结束位置，确定中间位置。
拿目标值与中间位置的值做比较，假如目标值大于中间位置取值，则起始位置为中间位置加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