thuật toán chia để trị

mảng có thứ tự tăng dần, tìm x, nó bị sai kq, e nhập x ngoài giá trị của mảng nó cũng bảo tồn tạo x trong mảng, nhập x thuộc phần tử của mảng nó cũng bảo tồn tại x trong mảng. mà e ko bit nó sai chỗ nào nữa
// chia de tri tim kiem x trong mang.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
using namespace std;

bool timx(int a[], int x, int n)
{ 
	int left = 0;
	int right = n - 1;
	while (left <= right)
	{
		int mid = (left + right) / 2;
		if (x = a[mid])
		{
			return 1;
		}
		else if (x < a[mid])
			right = mid - 1;
		else
			left = mid + 1;
	}
	return -1;
	
}
int _tmain(int argc, _TCHAR* argv[])
{
	int x,mid;
	int a[] = { 1,2,3,4,5,6,7,8 };
	int n = 7;
	cout << "nhap x=";
	cin >> x;
	int k = timx(a, x,n);
	if (k == 1) cout << "ton tai x trong mang!";
	else if(k==-1) cout << "ko ton tai x trong mang!";
	

	return 0;
}

Khi đặt câu hỏi em cố gắng dành nhiều thời gian hơn để đưa giải thích về lỗi sai chứ. Em không nên chỉ bảo là bị sai kq. Dĩ nhiên với các bài dễ thì ổn, nhưng mình không nên cứ như thế hoài. Ví dụ em nên chỉ ra em nhập vào cái gì, em hi vọng sẽ in ra cái gì, nhưng nó in ra cái gì?

3 Likes

dạ, e xin lỗi, tại e cũng nhát hihi, ko có lần sau đâu a :stuck_out_tongue:

1 Like
if (x = a[mid]) // so sánh thì phải dùng ==
2 Likes

hàm bool nên trả về true/false

1 Like

Bổ sung thêm video về vụ này nếu @Long_Long chưa hiểu lý do

a ns e ms thấy, nhưng sửa rồi vẫn vậy ak a

Nếu vậy thì là lỗi khác, em nghiên cứu lại code của mình xem. Anh nghĩ có vài lỗi “cơ bản” giống vậy nữa đấy.

bạn nên cập nhật tiếp bài viết của bạn theo hướng dẫn của anh Đạt nhé :smile:

Mình thấy được một chỗ là

if(x == a[mid])

:slight_smile: hy vọng giúp ích…

zạ, e hiu rồi a ĐẠT, hay quên cái này lắm, e bị mấy lần rồi mà ko rút dc kinh nghiệm

mọi nguoi cho e hỏi, hàm bool nhất quyết phải trả về true vs false ạ. tại e sửa theo a @david15894 thi chay đúng. liệu e muốn nó trả về 1 vs -1 có sai ko

e trả về 1 or 0 cũng đúng, nhưng a vs -1 là sai, ai giải thik cho e khi nào nên trả về giá trị nào đi ạ, e bị đơ phần này

Cái đó hình như là tùy vào bạn quy định thôi :slight_smile: thường thì thế này nếu tìm thấy giá trị đó thì bạn sẽ trả về 1, không tìm thấy thì trả về 0

đơn giản là vì -1 không có nghĩa gì cả. Thư viện của c++ định nghĩa sẵn TRUE là 1, FALSE là 0 (giống define ấy)
còn c thì phải khai báo thư viện mới dùng key TRUE FALSE được.
Cơ mà bài tìm kiếm nhị phân này thì nên trả về là kiểu int là vị trí của x luôn (return -1 nếu không tìm thấy) :smile:

1 Like

mới học thì nên code cẩn thận, nên dùng “{ }” (bracket) đầy đủ nhé.

1 Like

để e nghiên cứu, bài gốc của nó là tìm x trong mảng, trong đó mảng chia làm hai phần, n1 lẽ tăng dần, n2 chẵn giảm dần, vì e học qua qua nên ko hiu về mấy thuật toán này, nên mới phải làm bài chia để trị này lấy ấy tưởng để code bài gốc nữa. hihi

Theo như em thấy thì đây là Binary Search bình thường chứ đâu phải chia để trị đâu nhỉ ?

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?