Introduction
This is an introduction of Straight min max algorithm.
TLDR: The key idea of the video is that binary search is an efficient algorithm for finding elements in a sorted array by dividing the array and recursively searching for the desired element. 1. 💡 Binary search is an algorithm that optimizes the search for minimum and maximum elements in a sorted array by dividing the array into two parts and recursively searching for the desired element. 2. 🔍 Binary search is a more efficient algorithm than straight min max as it divides the array and applies an algorithm to search for a specific element. 3. 🔍 If there is only one element in the input and it matches the element being searched, return its position; otherwise, return -1 to indicate that the element is not present in the array. 4. 🔍 The algorithm finds the middle element of an array and checks if it is equal to the desired element, returning the index if it is present. 5. 🔍 If the element being searched is less than the middle element of the sorted array, the algorithm recursively searches the left side of the array; otherwise, it searches the right side until the element is found or determined to be absent. 6. 💡 Binary search algorithm has a time complexity of order of one for dividing an array and finding the mid, and takes t n time for searching n elements. 7. 💡 The time complexity of the algorithm is determined by the recurrence relation, which can be expressed as t(n) = t(n/2)^k + k*c, where k is the number of times the algorithm is executed and c is a constant. 8. 🔍 Binary search has a time complexity of log n, making it more efficient than linear search for finding elements in a sorted array. Summary for https://youtu.be/EufjD-flLZE by www.eightify.appwhats
#include <iostream>
using namespace std;
//i ->begining and j -> middle element and x is the element we want to find
int binarySearch(int arr[],int i,int j,int x){
if(i == j){
if(arr[i]==x)
return i;
else
return -1;
}
else{
int mid = (i + j) /2;
if (arr[mid]==x)
return mid;
else
if(x<arr[mid])
return binarySearch(arr,i,mid-1,x);
else
return binarySearch(arr,mid+1,j,x);
}
}
int main(){
int arr[5] = {10,20,30,40,50};
int t = binarySearch(arr,0 ,4,30);
if (t != -1)
cout << "Element Found At Position " << t << endl;
else
cout << "Element not found." << endl;
}
Output:
Element found at position 2.