top of page
Caută
Poza scriitoruluioanaunciuleanu

Binary Search in C++



The binary search algorithm is widely used in programming. It requires that the array in which we search for the value to be sorted. So, we apply this search algorithm only on a sorted array. This algorithm is all about dividing in half (divide and conquer) until the element is found, or there are no more elements in the array to apply this mechanism.


Knowing our target number, we divide the array in half. If the searched number matches the item in the middle of the array, then the search is over. If the target is higher than the value from the middle of the array, then the search continues in the right side of the array, diving it again. This process continues repeatedly until we find the value or the array ends.



// Binary Search

#include <iostream>
using namespace std;

int binarySearch(int arrayOfNumbers[], int searchForNumber, int left, int right)
{
	if (right >= left)
	{
		int middle = left + (right - left) / 2;

		if (arrayOfNumbers[middle] == searchForNumber)
        {
            printf("The number %d is found at index %d", searchForNumber, middle);
            return middle;
        }

		if (arrayOfNumbers[middle] > searchForNumber)
        {
            return binarySearch(arrayOfNumbers, searchForNumber, left, middle - 1);
        }
		return binarySearch(arrayOfNumbers, searchForNumber, middle + 1, right);
	}

	printf("The number %d was not found in the array", searchForNumber);
	return -1;
}

int main(void)
{
	int arrayOfNumbers[] = {1, 6, 9, 15, 17, 21, 30, 48, 61, 99};
	int searchForNumber = 30;

	int numberOfElements = sizeof(arrayOfNumbers) / sizeof(arrayOfNumbers[0]);
	int result = binarySearch(arrayOfNumbers, searchForNumber, 0, numberOfElements - 1);
}

24 afișări0 comentarii

Postări recente

Afișează-le pe toate

Tiling Problem in JAVA

You can use a board that is 2 x n size. The tiles are of size 2 x 1. Count the number of ways to tile the board. Tiles can be placed...

Comments


bottom of page