java shell算法_经典算法之二分查找（Python，Shell与Java实现）

Myth丶恋晨 2022-11-05 03:27 46阅读 0赞

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

![06cb5b3757827551b6ff41d080d0ffd2.png][]

2.2、基于shell实现

代码如下：

\#/bin/bash

function BinSearch()\{

declare -a arr=($1)

key=$2

start=0

end=\`expr $\{\#arr\[\*\]\} - 1\`

while \[ $\{start\} -le $\{end\} \]

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

done

arr=(1  2 3 5 7 9)

echo "Index of 2 is:$(BinSearch "$\{arr\[\*\]\}"  2)"

运行结果：

Index of 2 is:1

![896b45bdb710c3c685e97beddf7725de.png][]

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\]

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

![d89d44ac6f47d1c74dd6ea0b5cf7685d.png][]

![0b1331709591d260c1c78e86d0c51c18.png][]

[06cb5b3757827551b6ff41d080d0ffd2.png]: /images/20221023/80ed92e164db4a51bb3425d8f1bf4342.png
[896b45bdb710c3c685e97beddf7725de.png]: /images/20221023/199b4edcfcb44b108186dd0d39cacffc.png
[d89d44ac6f47d1c74dd6ea0b5cf7685d.png]: /images/20221023/c000c2f4f5a94d61ba9243f3120c4918.png
[0b1331709591d260c1c78e86d0c51c18.png]: /images/20221023/d9413841ad7b4325bbafabc8a99926b3.png