原创
查找过程演示:
在数组[130,150,170,190,210,230,250,270,290,310]中查找数字190,红色为二分线(折半线),灰色为查找区域,黑色为排除区域。
SYJ二分查找演示.gif二分查找优缺点:
二分查找(折半查找)优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。时间复杂度可以表示O(h)=O(log2n),以2为底,n的对数。比如数组长度为10,最多找4次。
objectIve-c实现代码:
#import <Foundation/Foundation.h>
int search(NSArray *array,int item){
int x = 1;
int low = 0;
int high = (int)[array count] - 1;
while (low <= high) {
NSLog(@"第%d次比较",x);
x++;
int mid = (high+low)/2;
if(item == [array[mid] intValue]){
NSLog(@"%d找到了,在第%d个位置",item,mid);
return mid;
}else if(item < [array[mid] intValue]){
NSLog(@"%d比%d大,继续查找",[array[mid] intValue],item);
high = mid-1;
}else{
NSLog(@"%d比%d小,继续查找",[array[mid] intValue],item);
low = mid+1;
}
}
return -1;
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
NSLog(@"请输入要查询的数字:");
int x;
scanf("%d",&x);
NSArray *array = @[@1,@3,@5,@7,@9,@11,@13,@15,@17,@19,@21,@23,@25];
int jieguo = search(array,x);
if(jieguo == -1){
NSLog(@"没找到要查找的数字");
}
}
return 0;
}
运行截图:
1.pngjava实现代码:
import java.util.Scanner;
public class PaiXu{
public static void main(String[] args){
Integer[] haha = {1,3,5,7,9,11,13,15,17,19,21,23,25,27};
Scanner sc = new Scanner(System.in);
System.out.println("请输入您要查找的值:");
int z = sc.nextInt();
int y = binarySearch(haha,z);
if(y == -1){
System.out.println("要查找的值不存在");
}
}
public static int binarySearch(Integer[] srcArray,int des){
int x = 1;
int low = 0;
int high = srcArray.length-1;
while(low<=high){
System.out.println("第"+x+"次比较");
x++;
int mid = (high+low)/2;
if(des == srcArray[mid]){
System.out.println(des+"找到了,在第"+mid+"个位置");
return mid;
}else if(des < srcArray[mid]){
System.out.println(srcArray[mid]+"比"+des+"大,继续查找");
high = mid-1;
}else{
System.out.println(srcArray[mid]+"比"+des+"小,继续查找");
low = mid+1;
}
}
return -1;
}
}
运行截图:
2.pngPython实现代码:
def binary_search(list,item):
x = 1
low = 0
high = len(list)-1
while low <= high:
print('第%d次比较'%x)
x=x+1
mid = (low+high)//2
guess = list[mid]
if guess == item:
print('找到了,在第%d个位置'%mid)
return mid
if guess > item:
print('%d比%d大,继续查找'%(guess,item))
high = mid-1
else:
print('%d比%d小,继续查找'%(guess,item))
low = mid+1
print('找不到%d'%item)
return None
my_list = [1,3,5,7,9,11,13,15,17,19,21,23,25]
z = int(input('请输入要查找的数字:'))
binary_search(my_list,z)
运行截图:
scala实现代码:
object ErFen{
def main(args:Array[String]){
//var z:Array[Int] = new Array[Int](14);
//var z = new Array[Int](14);
var z = Array(1,3,5,7,9,11,13,15,17,19,21,23,25,27);
var y:Int = search(z,15);
if(y == -1){
println("要查找的值不存在");
}
}
def search(arr:Array[Int],des:Int):Int={
var x:Int = 1;
var low:Int = 0;
var high:Int = arr.length-1;
while(low <= high){
println("第"+x+"次比较");
x += 1;
var mid:Int = (high+low)/2;
if(des == arr(mid)){
println(des+"找到了,在第"+mid+"个位置");
return mid;
}else if(des < arr(mid)){
println(arr(mid)+"比"+des+"大,继续查找");
high = mid - 1;
}else{
println(arr(mid)+"比"+des+"小,继续查找");
low = mid + 1;
}
}
return -1;
}
}
网友评论