binary search
# Python3 Program for recursive binary search.
# Returns index of x in arr if present, else -1
def binarySearch (arr, l, r, x):
# Check base case
if r >= l:
mid = l + (r - l) // 2
# If element is present at the middle itself
if arr[mid] == x:
return mid
# If element is smaller than mid, then it
# can only be present in left subarray
elif arr[mid] > x:
return binarySearch(arr, l, mid-1, x)
# Else the element can only be present
# in right subarray
else:
return binarySearch(arr, mid + 1, r, x)
else:
# Element is not present in the array
return -1
# Driver Code
arr = [ 2, 3, 4, 10, 40 ]
x = 10
# Function call
result = binarySearch(arr, 0, len(arr)-1, x)
if result != -1:
print ("Element is present at index % d" % result)
else:
print ("Element is not present in array")
/* This is just the seaching function you need to write the required code.
Thank you. */
void searchNode(Node *root, int data)
{
if(root == NULL)
{
cout << "Tree is empty\n";
return;
}
queue<Node*> q;
q.push(root);
while(!q.empty())
{
Node *temp = q.front();
q.pop();
if(temp->data == data)
{
cout << "Node found\n";
return;
}
if(temp->left != NULL)
q.push(temp->left);
if(temp->right != NULL)
q.push(temp->right);
}
cout << "Node not found\n";
}
def binarySearch(arr, l, r, x):
while l <= r:
mid = l + (r - l) // 2;
# Check if x is present at mid
if arr[mid] == x:
return mid
# If x is greater, ignore left half
elif arr[mid] < x:
l = mid + 1
# If x is smaller, ignore right half
else:
r = mid - 1
# If we reach here, then the element
# was not present
return -1
# Driver Code
arr = [ 2, 3, 4, 10, 40 ]
x = 10
# Function call
result = binarySearch(arr, 0, len(arr)-1, x)
if result != -1:
print ("Element is present at index % d" % result)
else:
print ("Element is not present in array")
import java.util.Scanner;
public class Binarysearch {
public static void main(String[] args) {
int[] x= {1,2,3,4,5,6,7,8,9,10,16,18,20,21};
Scanner scan=new Scanner(System.in);
System.out.println("enter the key:");
int key=scan.nextInt();
int flag=0;
int low=0;
int high=x.length-1;
int mid=0;
while(low<=high)
{
mid=(low+high)/2;
if(key<x[mid])
{
high=mid-1;
}
else if(key>x[mid])
{
low=mid+1;
}
else if(key==x[mid])
{
flag++;
System.out.println("found at index:"+mid);
break;
}
}
if(flag==0)
{
System.out.println("Not found");
}
}
}
// Binary Search using Iterative Approach
import java.io.*;
class Binary_Search
{
public static void main(String[] args) throws Exception
{
Binary_Search obj = new Binary_Search();
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
System.out.println("Insert the length of the Array : ");
int n = Integer.parseInt(br.readLine());
int arr[] = new int[n];
System.out.println("Insert elements into the array : ");
for(int i=0;i<n;i++)
{
arr[i] = Integer.parseInt(br.readLine());
}
System.out.println("Enter the num which you want to Search : ");
int num = Integer.parseInt(br.readLine());
obj.logic(arr,num);
}
void logic(int arr[],int num)
{
int r = arr.length - 1;
int l = 0;
int mid;
while(l<=r)
{
mid = l + (r-l)/2;
if(arr[mid] == num)
{
System.out.println("Number found at "+mid+"th index");
break;
}
else if(arr[mid]>num)
{
r = mid - 1;
}
else
{
l = mid + 1;
}
}
}
}