10. Binární vyhledávání
Pole nums je seřazené vzestupně. Vrať index prvku target, nebo -1, pokud v poli není.
Řešení má běžet v O(log n) – tedy binárním vyhledáváním, ne procházením celého pole.
Příklady
Vstup
nums = [-1, 0, 3, 5, 9, 12], target = 9Výstup
4Vstup
nums = [-1, 0, 3, 5, 9, 12], target = 2Výstup
-1Drž si hranice lo a hi a spočítej střed mid = (lo + hi) >> 1. Když je nums[mid] menší než target, hledej vpravo (lo = mid + 1), jinak vlevo (hi = mid - 1).
1function search(nums: number[], target: number): number {2 let lo = 0;3 let hi = nums.length - 1;4 while (lo <= hi) {5 const mid = (lo + hi) >> 1;6 if (nums[mid] === target) return mid;7 if (nums[mid] < target) lo = mid + 1;8 else hi = mid - 1;9 }10 return -1;11}12