Answer to Question #294620 in C++ for Yaku

Question

1. Trace and comment each and every line of the C++ program below:

#include <iostream>

using namespace std;

int binarySearch(int arr[], int left, int right, int num)

{

if (right >= left) {

int mid = left + (right - left) / 2;

if (arr[mid] == num)

return mid;

if (arr[mid] > num)

return binarySearch(arr, left, mid - 1, num);

return binarySearch(arr, mid + 1, right, num);

}

return -1;

}

int main(void)

{

int arr[] = { 2, 3, 4, 8, 10, 40 };

int check = 40;

int n = sizeof(arr) / sizeof(arr[0]);

int result = binarySearch(arr, 0, n - 1, check);

(result == -1)

? cout << "Element is not present in array"

: cout << "Element is present at index " << result;

return 0;

}

Answer 1

#include <iostream> // include file that contains methods for writing in concole


using namespace std; // if we do not write this string, we have to write std::cout instead of cout


/* 
	find num in arr from arr[left] to arr[right]
	note: arr must be sorted in ascending order


	Because arr must be sorted in ansending order, 
		we can make a conclusion that
		than the smaller the index, the smaller the value.


	Binary search algorithm means 
		that we take sequence from arr[left] to arr[right]
		after that we devide this sequence to two smaller sequences,
		left sequence containes smallest numbers,
		right sequence containes biggest numbers
		mid of original sequence is separator of these two sequences.
		note: mid is greater than any number from left sequence
			  and less than any number from right sequence


*/
int binarySearch(int arr[], int left, int right, int num)


{
	// if right < left then sequence from arr[left] to arr[right] does not contain any number
	if (right >= left) {
		// find the mid index in slice [left; right]
		int mid = left + (right - left) / 2;


		// if arr[mid] is equal to num, return num
		if (arr[mid] == num)


			return mid;
		// if arr[mid] > num, num can locate only in left sequence
		if (arr[mid] > num)


			return binarySearch(arr, left, mid - 1, num);
		// if arr[mid] < num (only in this case the program reaches this line)
		return binarySearch(arr, mid + 1, right, num);


	}
	// because num must be greater then arr[left] and less then arr[right], but arr[right] < arr[left]
	return -1;


}


int main(void)


{
	// we put this array in the binarySearch function
	int arr[] = { 2, 3, 4, 8, 10, 40 };
	// we try to find this number
	int check = 40;
	// n is amount of elements in arr
	int n = sizeof(arr) / sizeof(arr[0]);
	// result is the result of binarySearch funcion
	int result = binarySearch(arr, 0, n - 1, check);
	// if result == -1
	(result == -1)
		// then check is not contained in arr
		? cout << "Element is not present in array"
		// else print index of check
		: cout << "Element is present at index " << result;


	return 0;


}