Viết chương trình hoàn chỉnh nhập một dãy số đơn điệu tăng từ bàn phím, các số cách nhau

Giải Chuyên đề Tin học 11 Kết nối tri thức Bài 6: Ý tưởng và kĩ thuật chia để trị

Luyện tập 1 trang 32 Chuyên đề Tin học 11:Viết chương trình hoàn chỉnh nhập một dãy số đơn điệu tăng từ bàn phím, các số cách nhau bởi dấu cách. Sau đó, nhập số K bất kì từ bàn phím và thực hiện việc tìm kiếm số K trong dãy trên. Nếu tìm thấy thì trả lại chỉ số của phần tử có giá trị K, ngược lại trả về – 1

Lời giải:

Em sẽ thực hiện các bước sau:

1. Nhập dãy số đơn điệu tăng từ bàn phím, các số cách nhau bởi dấu cách.

2. Nhập số K cần tìm kiếm từ bàn phím.

3. Thiết lập biến low là 0 và biến high là độ dài của dãy trừ 1.

4. Trong khi low <= high, thực hiện các bước sau:

- Thiết lập biến mid là phần tử ở giữa của dãy từ low đến high.

- Nếu arr[mid] == k, trả về mid.

- Nếu arr[mid] > k, thực hiện tìm kiếm trên nửa đầu của dãy bằng cách đặt high bằng mid-- Nếu arr[mid] < k, thực hiện tìm kiếm trên nửa sau của dãy bằng cách đặt low bằng mid+1.

5. Nếu không tìm thấy k trong dãy, trả về -1.