转载

经典算法之二分查找(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
正文到此结束
Loading...