二分法查找（有序数组）JavaScript

来源：爱站旅游

导读二分法查找（有序数组）JavaScript

<!DOCTYPE html>
<html>
<head>
	<title></title>
</head>
<body>
<script type="text/javascript">
	
	// 二分法查找 有序 数组
	function binarySearch(arr, target){
		let left = 0;
		let right = arr.length-1;
		let m = Math.floor((left + right) / 2);
		let sortTag = arr[left] <= arr[right]; // 这样不管升序还是降序都可以支持
		while( left < right && arr[m] !== target ){
			if( arr[m] > target ){
				sortTag && (right = m - 1);
				!sortTag && (left = m + 1);
			}else{
				sortTag && (left = m + 1);
				!sortTag && (right = m - 1);
			}
			m = Math.floor((left + right) / 2);
		}
		if( arr[m] === target ){
			return m;
		}else{
			return -1;
		}
	}
	console.log(binarySearch([1, 3, 4, 6, 6, 6, 8, 8, 9, 9, 9, 12], 12));

</script>
</body>
</html>

升序降序都适用
事件复杂度O(log2n)

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

Top