1. 二分法查找
前提: 数据是排好序的。
题设:给出一个有序arr,从中找出key,arr的区间是array[ low , higt].
步骤:
(1)mid=(low+high)/2
(2)array[mid]与key 比较,若相等,返回mid。
(3)if array[mid]>key,则在arryay[low,mid-1]查找
if array[mid]<key,则在array[mid+1,higt]查找
(4)重复(1)(2)(3)
2. 题目:用js实现二分法查找。要求:从浏览器中输入一个无序的数组以及一个需要查找的数字,输出要查找数字在排序后的数字中的位置。
以下程序大体实现了该功能,有些还没有完善。
需要注意的有以下几点:
(1)在浏览器输入1,2,0,3,10 后,实际上存储的是一个字符串“1,2,0,3,10”,所以需要使用split()将其转换为字符串数组:[“1”,“2”,“0”,“3”,“10”]
(2)使用map(function(data){return +data;})对每一个元素进行类型转换,将字符串数组转换为整型数组。
(3)不能使用sort()直接对数组进行排序,要结合campare函数。
(4)parseInt()将数组的字符串转换为整型。
(5)Math.floor()向下取整。
(6) 当要查找的数字不是输入数组中包含,会出现以下错误:
所以进行:if(data==key)判断。
1 var arr = prompt("请输入一个数组(以“,”隔开):").split(",").map(function(data){ 2 return +data;}).sort(compare); 3 console.log("输入的数组,排序后是:"+arr); 4 5 var key=parseInt(prompt("请输入一个要查找的数字:")); 6 console.log("要查找的数字是:"+key); 7 8 var low=0,high=arr.length-1,mid; 9 10 arr.map(function(data){ 11 if(data==key){ 12 console.log("您要查找的数字排在第 "+fun(arr,key,low,high)+" 位"); 13 } 14 }) 15 16 function compare(value1,value2){ 17 if(value1<value2){ 18 return -1; 19 }else if(value1>value2){ 20 return 1; 21 }else{ 22 return 0; 23 } 24 } 25 26 function fun(arr,key,low,high){ 27 mid=Math.floor((low+high)/2); 28 if(arr[mid]==key){ 29 return mid; 30 }else if(arr[mid]<key){ 31 low=mid+1; 32 return fun(arr,key,low,high); 33 }else{ 34 high=mid-1; 35 return fun(arr,key,low,high); 36 } 37 }
C语言(递归)
1 #include <stdio.h> 2 #include <malloc.h> 3 int BinarySearch(int arr[], int key, int low, int high){ 4 int mid = (low + high) / 2; 5 if(key == arr[mid]){ 6 printf("The index of the key is: %d ",mid); 7 }else if(key > arr[mid]){ 8 low = mid + 1; 9 BinarySearch(arr, key, low, high); 10 }else{ 11 high = mid - 1; 12 BinarySearch(arr, key, low, high); 13 } 14 15 return 0; 16 } 17 int main(){ 18 int len, i, *arr, key; 19 printf("The length is: "); 20 scanf("%d", &len); 21 arr = (int*)malloc(sizeof(int)*len); 22 printf("Please enter an ordered array: "); 23 for(i=0; i<len; i++){ 24 scanf("%d",&arr[i]); 25 } 26 printf("Please enter the number you want to find:"); 27 scanf("%d",&key); 28 BinarySearch(arr, key, 0, len-1); 29 return 0; 30 }
C语言
1 #include <stdio.h> 2 #include <malloc.h> 3 int BinarySearch(int arr[], int key, int low, int high){ 4 while(low <= high){ 5 int mid = (low +high) / 2; 6 if(key > arr[mid]){ 7 low = mid + 1; 8 }else if(key < arr[mid]){ 9 high = mid + 1; 10 }else{ 11 return mid; 12 } 13 } 14 15 return -1; 16 } 17 int main(){ 18 int len, i, *arr, key, res; 19 printf("The length is: "); 20 scanf("%d", &len); 21 arr = (int*)malloc(sizeof(int)*len); 22 printf("Please enter an ordered array: "); 23 for(i=0; i<len; i++){ 24 scanf("%d",&arr[i]); 25 } 26 printf("Please enter the number you want to find:"); 27 scanf("%d",&key); 28 res = BinarySearch(arr, key, 0, len-1); 29 if(res < 0){ 30 printf("The key is no in array! "); 31 }else{ 32 printf("The index of the key is: %d ",res); 33 } 34 return 0; 35 }