Một đề bài mà Đạt mới đọc thấy hay hay đó là implement binary search bằng loop thay vì đệ quy. Ngày xưa lúc mới học binary search thì toàn làm bằng đệ quy rồi vứt luôn. Nên giờ code lại binary search thấy cũng hơi gượng tay. Có thời gian làm lại mấy bài này luyện code tay cũng tốt 
Coi như luyện tập hàm binary search, không google nhé 
// trả về chỉ số phần tử có giá trị bằng key
// return -1 nếu không tìm thấy
// mảng tăng dần, bắt đầu từ 0
int binSearch(int arr[], int n, int key){
int left, right, mid;
left = 0, right = n-1;
while (left <= right){
mid = (left + right)/2;
if (arr[mid] == key)
return mid;
if (arr[mid] > key)
right = mid - 1;
else
left = mid + 1;
}
return -1;
}Này là code mà mình hay dùng trong java:
/**
* Trả về vị trí của @key trong @arr. Nếu không tìm thấy thì trả về giá trị âm
* R sao cho insert_index = ~R
*/
int binarySearch(int []arr, int key) {
int low = 0, hi = arr.length - 1;
while(low <= hi) {
int mid = (low + hi) >>> 1;
if(arr[mid] == key)
return mid;
if(arr[mid] < key)
low = mid + 1;
else
hi = mid - 1;
}
return -(low - 1);
}
Em thì ngược lại, code binary search bằng đệ quy thấy gượng tay
Cho em hỏi có sự khác nhau giữa:
int binSearch(int arr[], int n, int key)
{
int left, right, mid;
left = 0, right = n - 1;
while (left <= right) {
...
}
}
với
int binSearch(int arr[], int n, int key)
{
int left, right;
left = 0, right = n - 1;
while (left <= right) {
int mid;
...
}
}
không ạ ? (biến mid nằm ở ngoài và trong vòng while) (về thời gian chạy)
nếu mà soi kỹ thì đặt trong tốn thêm 1 tí thời gian hơn, vì mỗi lần lặp, nó phải thực hiện 2 việc tạo và hủy biến. Nhưng chênh lệch thực tế gần bằng 0, vì số lần lặp chỉ là log2(N), nếu N = 109 thì cũng chỉ là 30 lần lặp
cho em hỏi chỉnh sửa binary search như thế nào để tìm số nhỏ nhất lớn hơn số cần tìm và só lớn nhất nhỏ hơn số cần tìm vậy?
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?