二分法查找的实现 | JavaScript | PHP | Kotlin

二分法高中就学过了，今天复习算法时候又加固一下，我们首先获取最小位于最大位，然后计算中位（取整）

如果带搜索的值 waitValue > array[m] 说明在中位的右侧相反则左侧。

前提条件是：

1.递增的数组

2.整数（方便演示）

JavaScript:正常查找

1
2
3
4
5
6
7
8
function normalSearch(searchKey,arrayData){
	for (let i = 0; i < arrayData.length; i++) {
		if(arrayData[i] == searchKey){
			return i
		}
	}	
	return -1;
}

null

JavaScript:二分法查找，这里用了ceil取整数，因为JS会保留小数部分，使用闭包传入参数自执行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(function(searchKey,arrayData){
	let start = 0,end = arrayData.length-1;

	while(start <= end){
		let mKey = Math.ceil((start + end)/2);
		if(searchKey == arrayData[mKey]){
			console.log(mKey);
			return mKey;
		}else if(searchKey > arrayData[mKey]){
			start = mKey + 1;
		}else{
			end = mKey-1;
		}

	}
	console.log(-1);
	return ;
})(3,[1,2,3,4,5,6])

null

PHP二分法查找 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function binarySearch($arr,$value){

	$left = 0;
	$count = count($arr);
	$right = $count - 1;
	
	
	while ($left <= $right) {
		$m =intval(($left + $right)/2);
		if($value == $arr[$m]){
			return $m;
		}
		if($arr[$m] < $value  ){
			$left = $m + 1;
		}else{
			$right = $m-1;
		}
		

	}
	return -1;
	
}
echo binarySearch([1,2,3,4,5],2);

null

Kotlin 二分法查询 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
fun main(){

        fun binarySearch(arr:IntArray,value:Int):Int{
            var left = 0
            var right = arr.size - 1
            while (left <= right){
                val m = (left + right)/2
                when{
                    value == arr[m] ->{
                        println("找到:$m")
                        return m
                    }
                    value > arr[m] ->{
                        left = m + 1
                    }
                    else ->{
                        right = m - 1
                    }

                }
            }
            println("没有")
            return 1
        }
        binarySearch(intArrayOf(1,2,3,4,5),3)


}

null