经典算法之二分查找(Python,Shell与Java实现)

1、算法思想

二分查找采用分而治之的思想。 要求被查找的集合必须是有序的。 主要思路:

  1. 根据起始位置和结束位置,确定中间位置。
  2. 拿目标值与中间位置的值做比较,假如目标值大于中间位置取值,则起始位置为中间位置加1。
  3. 假如目标值小于中间位置取值,则结束位置为中间位置减1。
  4. 直至起始位置小于等于结束位置,找到目标值的位置即索引

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

经典算法之二分查找(Python,Shell与Java实现)

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

经典算法之二分查找(Python,Shell与Java实现)

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

经典算法之二分查找(Python,Shell与Java实现)

Linux公社的RSS地址https://www.linuxidc.com/rssFeed.aspx

本文永久更新链接地址: https://www.linuxidc.com/Linux/2019-04/158113.htm

原文 

https://www.linuxidc.com/Linux/2019-04/158113.htm

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 经典算法之二分查找(Python,Shell与Java实现)

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址