TypeScriptbinary-search.ts
Copy
1
// Standard binary search: O(log n)
2
function binarySearch(arr: number[], target: number): number {
3
  let left = 0, right = arr.length - 1;
4
  while (left <= right) {
5
    const mid = (left + right) >>> 1;
6
    if (arr[mid] === target) return mid;
7
    if (arr[mid] < target) left = mid + 1;
8
    else right = mid - 1;
9
  }
10
  return -1;
11
}
12
 
13
// Find FIRST occurrence (lower bound)
14
function findFirst(arr: number[], target: number): number {
15
  let left = 0, right = arr.length - 1, result = -1;
16
  while (left <= right) {
17
    const mid = (left + right) >>> 1;
18
    if (arr[mid] === target) { result = mid; right = mid - 1; }
19
    else if (arr[mid] < target) left = mid + 1;
20
    else right = mid - 1;
21
  }
22
  return result;
23
}
24
 
25
// Find LAST occurrence (upper bound)
26
function findLast(arr: number[], target: number): number {
27
  let left = 0, right = arr.length - 1, result = -1;
28
  while (left <= right) {
29
    const mid = (left + right) >>> 1;
30
    if (arr[mid] === target) { result = mid; left = mid + 1; }
31
    else if (arr[mid] < target) left = mid + 1;
32
    else right = mid - 1;
33
  }
34
  return result;
35
}
36
 
37
// Test
38
const arr = [1, 3, 3, 3, 5, 7, 9];
39
console.log(binarySearch(arr, 3));  // 1, 2, or 3 (any match)
40
console.log(findFirst(arr, 3));     // 1
41
console.log(findLast(arr, 3));      // 3
42
console.log(binarySearch(arr, 4));  // -1