線形探索が二分探索より速い場面とは

単純に考えると探索範囲 N とすると、探索値がlog2(N)以内にあれば線形探索が優位でしょう。例えば N が256なら探索値が8番目までに見つかるような場合です。
しかし実際の所、二分探索は分岐や位置計算が必要なので、もう少し上ぶれしそうな気がします。それではJavaScriptで検証してみます。

探索値が均等に分布

意外にも N が60程度まではほぼ互角

for(let n=256,run=n;--n;run++){
	let A=Uint8Array.from(Array(n),(a,b)=>b), t=new Date, u;
	//線形探索
	for(let r=run;r--;)
		for(let a=n,b;a--;)
			for(b=0;A[b]!==a;)++b;
	u=new Date;t=u-t;
	//二分探索
	for(let r=run;r--;)
		for(let a=n,b,c,d;a--;)
			for(b=0,c=n;b<c;)A[d=b+c>>1]<a?b=d+1:c=d;
	document.write(n,": ",t,"ms ",new Date-u,"ms<br>")
}

探索値が中央付近に集中

N が40程度まではほぼ互角

for(let n=256,run=n;--n;run++){
	let A=Uint8Array.from(Array(n),(a,b)=>b), t=new Date, u;
	//線形探索
	for(let r=run;r--;)
		for(let a=n,b,e=n>>1;a--;)
			for(b=0;A[b]!==e;)++b;
	u=new Date;t=u-t;
	//二分探索
	for(let r=run;r--;)
		for(let a=n,b,c,d,e=n>>1;a--;)
			for(b=0,c=n;b<c;)A[d=b+c>>1]<e?b=d+1:c=d;
	document.write(n,": ",t,"ms ",new Date-u,"ms<br>")
}

探索値が最後尾に集中

N が30程度まではほぼ互角

for(let n=256,run=n;--n;run++){
	let A=Uint8Array.from(Array(n),(a,b)=>b), t=new Date, u;
	//線形探索
	for(let r=run;r--;)
		for(let a=n,b,e=n-1;a--;)
			for(b=0;A[b]!==e;)++b;
	u=new Date;t=u-t;
	//二分探索
	for(let r=run;r--;)
		for(let a=n,b,c,d,e=n-1;a--;)
			for(b=0,c=n;b<c;)A[d=b+c>>1]<e?b=d+1:c=d;
	document.write(n,": ",t,"ms ",new Date-u,"ms<br>")
}

探索値が先頭に集中

さすがに線形探索の方が速いに決まっています

for(let n=256,run=n;--n;run++){
	let A=Uint8Array.from(Array(n),(a,b)=>b), t=new Date, u;
	//線形探索
	for(let r=run;r--;)
		for(let a=n,b,e=0;a--;)
			for(b=0;A[b]!==e;)++b;
	u=new Date;t=u-t;
	//二分探索
	for(let r=run;r--;)
		for(let a=n,b,c,d,e=0;a--;)
			for(b=0,c=n;b<c;)A[d=b+c>>1]<e?b=d+1:c=d;
	document.write(n,": ",t,"ms ",new Date-u,"ms<br>")
}

検証環境

Windows7 Google Chrome 109.0.5414.120