tìm kiếm nhị phân, còn được gọi là tìm kiếm nửa khoảng, tìm kiếm logarit, hoặc tìm kiếm nhị phân, là một thuật toán tìm kiếm tìm vị trí của giá trị đích trong một mảng được sắp xếp. Tìm kiếm nhị phân so sánh giá trị đích với phần tử giữa của mảng. Nếu chúng không bằng nhau, một nửa trong đó mục tiêu không thể nói dối sẽ bị loại bỏ và tiếp tục tìm kiếm trên nửa còn lại, một lần nữa lấy phần tử ở giữa để so sánh với giá trị mục tiêu và lặp lại điều này cho đến khi tìm thấy giá trị mục tiêu. Nếu kết thúc tìm kiếm với một nửa còn lại trống, thì mục tiêu không có trong mảng. Mặc dù ý tưởng đơn giản nhưng việc triển khai tìm kiếm nhị phân một cách chính xác đòi hỏi phải chú ý đến một số điều kiện tinh tế về điều kiện thoát và tính toán điểm giữa của nó, đặc biệt nếu các giá trị trong mảng không phải là tất cả các số nguyên trong phạm vi.
Tìm kiếm nhị phân là thuật toán tìm kiếm phổ biến nhất. Nó hiệu quả và cũng là một trong những kỹ thuật được sử dụng phổ biến nhất được sử dụng để giải quyết vấn đề.
Nếu tất cả các tên trên thế giới được viết ra cùng nhau theo thứ tự và bạn muốn tìm kiếm vị trí của một tên cụ thể, tìm kiếm nhị phân sẽ thực hiện điều này trong tối đa 35 lần lặp.
Tìm kiếm nhị phân chỉ hoạt động trên một tập hợp các phần tử đã được sắp xếp. Để sử dụng tìm kiếm nhị phân trên một tập hợp, trước tiên tập hợp đó phải được sắp xếp.
Khi tìm kiếm nhị phân được sử dụng để thực hiện các hoạt động trên một tập hợp đã sắp xếp, số lần lặp lại luôn có thể được giảm xuống trên cơ sở giá trị đang được tìm kiếm.
Chúng ta hãy xem xét mảng sau -
Bằng cách sử dụng tìm kiếm tuyến tính, vị trí của phần tử 8 sẽ được xác định trong lần lặp thứ 9.
Hãy xem làm thế nào để giảm số lần lặp lại bằng cách sử dụng tìm kiếm nhị phân. Trước khi bắt đầu tìm kiếm, chúng ta cần biết điểm bắt đầu và kết thúc của phạm vi. Hãy gọi chúng là Thấp và Cao.
Low = 0 High = n-1
Bây giờ, hãy so sánh giá trị tìm kiếm K với phần tử nằm ở trung vị của giới hạn dưới và giới hạn trên. Nếu giá trị K lớn hơn, hãy tăng giới hạn dưới, nếu không, hãy giảm giới hạn trên.
Đề cập đến hình ảnh ở trên, giới hạn dưới là 0 và giới hạn trên là 9
Trung vị của giới hạn dưới và giới hạn trên là (giới hạn dưới + giới hạn trên) / 2 =4. Đây a [4] =4. Giá trị 4> 2, là giá trị mà bạn đang tìm kiếm. Do đó, chúng tôi không cần thực hiện tìm kiếm trên bất kỳ phần tử nào vượt quá 4 vì các phần tử vượt quá nó rõ ràng sẽ lớn hơn 2.
Do đó, chúng ta luôn có thể giảm giới hạn trên của mảng xuống vị trí của phần tử 4. Bây giờ, chúng ta làm theo quy trình tương tự trên cùng một mảng với các giá trị sau -
Low: 0 High: 3
Lặp lại quy trình này một cách đệ quy cho đến khi Thấp> Cao. Nếu tại bất kỳ lần lặp nào, chúng ta nhận được khóa [mid] =, chúng ta trả về giá trị là giữa. Đây là vị trí của khóa trong mảng. Nếu khóa không có trong mảng, chúng tôi trả về −1.
Ví dụ
int binarySearch(int low,int high,int key){
while(low<=high){
int mid=(low+high)/2;
if(a[mid]<key){
low=mid+1;
}
else if(a[mid]>key){
high=mid-1;
}
else{
return mid;
}
}
return -1; //key not found
}