Binary Search
Tags:
Hard
Skills:
Binary Search
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Theory Data Structure And Algorithms
No headings found
Related Posts
Theory Data Structure And Algorithms
Binary Search là một thuật toán tìm kiếm nhanh hoạt động trên nguyên tắc “Chia để trị”. Thuật toán này chỉ hoạt động hiệu quả khi mảng đã được sắp xếp.
Nguyên lý hoạt động của Binary Search
Time and space complexity
Bisec_left
1from bisect import bisect_left
2arr = [1, 2, 4, 4, 5]
3print(bisect_left(arr, 4)) # Output: 2 (vị trí đầu tiên của số 4)
4print(bisect_left(arr, 3)) # Output: 2 (vị trí chèn của số 3)Bisec_right
1from bisect import bisect_right
2arr = [1, 2, 4, 4, 5]
3print(bisect_right(arr, 4)) # Output: 4 (vị trí sau số cuối cùng là số 4)
4print(bisect_right(arr, 3)) # Output: 2 (vị trí chèn của số 3)Implement Typescript
1function binarySearch(arr: number[], target: number): number {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while(left <= right) {
6 const mid = left + Math.floor((right - left) / 2);
7
8 if(arr[mid] === target) {
9 return mid;
10 else if (arr[mid] > target) {
11 left = mid + 1;
12 } else {
13 right = mid - 1;
14 }
15 }
16
17 return -1;
18}1function bisectLeft(arr: number[], target: number): number {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left <= right) {
6 const mid = left + Math.floor((right - left) / 2);
7
8 if(arr[mid] < target) {
9 left = mid + 1;
10 } else {
11 right = mid - 1;
12 }
13 }
14
15 return left;
16}1function bisectRight(arr: number[], target: number): number {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left <= right) {
6 const mid = left + Math.floor((right - left) / 2);
7
8 if(arr[mid] <= target) {
9 left = mid + 1;
10 } else {
11 right = mid - 1;
12 }
13 }
14
15 return left;
16}right = mid - 1 và right = mid phụ thuộc vào mục tiêu cụ thể của thuật toán và cách bạn muốn xử lý các trường hợp biênarr[mid] > x, bạn sẽ cập nhật right = mid - 1 để loại bỏ mid và tất cả các phần tử bên phải của nómid trong phạm vi tìm kiếm vì có thể giá trị bạn đang tìm kiếm nằm ở đómid nhỏ hơn hoặc bằng giá trị mà bạn đang tìm kiếm. Điều này cho phép bạn kiểm tra lại mid trong các lần lặp tiếp theox mà arr[mid] ≤ x , bạn sẽ cập nhật right = mid để giữa lại mid trong phạm vi tìm kiếmleft ≤ right left ≤ right được sử dụng khi bạn muốn kiểm tra cả trường hợp left === right trong vòng lặp. Điều này thường xảy ra khi cần xét đến phần tử cuối cùng trong phạm vi tìm kiếmleft < right?left < right được sử dụng khi bạn không cần kiểm tra trường hợp left === right trong vòng lặp. Thay vào đó, bạn để vòng lặp dừng ngay khi phạm vị chỉ còn 1 phần tử