Tại mỗi bước, ta so sánh x với phần tử đứng giữa trong mảng đang tìm kiếm, dựa vào kết quả so sánh này mà ta quyết định giới hạn dãy tìm kiếm ở nữa dưới hay nữa trên của dãy tìm kiếm hiện hành.
Các bước thực hiện thuật toán
Giả sử mảng tìm kiếm hiện hành bao gồm các phần tử nằm trong aleft, aright. Các bước của giải thuật như sau:
Bước 1: Gán left=0; right=n-1;
Bước 2:
mid=[left+right]/2;//chỉ số phần tử giữa mảng hiện hành
So sánh a[mid] với x. Có 3 khả năng:
- * a[mid] == x -> tìm thấy -> Dừng.
- a[mid] > x thì gán right=mid-1;//tìm tiếp x trong mảng con a[left],..,a[mid-1]
- a[mid] < x thì gán left=mid+1;//tìm tiếp x trong mảng con a[mid+1],..,a[right]
Bước 3: Nếu left