```#include <stdio.h>
int binarySearch(int a[], int beg, int end, int val)
{
int mid;
if(end >= beg)
{        mid = (beg + end)/2;
/* if the item to be searched is present at middle */
if(a[mid] == val)
{
return mid+1;
}
/* if the item to be searched is smaller than middle, then it can only be in left subarray */
else if(a[mid] < val)
{
return binarySearch(a, mid+1, end, val);
}
/* if the item to be searched is greater than middle, then it can only be in right subarray */
else
{
return binarySearch(a, beg, mid-1, val);
}
}
return -1;
}
int main() {
int a[] = {11, 14, 25, 30, 40, 41, 52, 57, 70}; // given array
int val = 40; // value to be searched
int n = sizeof(a) / sizeof(a[0]); // size of array
int res = binarySearch(a, 0, n-1, val); // Store result
printf("The elements of the array are - ");
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\nElement to be searched is - %d", val);
if (res == -1)
printf("\nElement is not present in the array");
else
printf("\nElement is present at %d position of array", res);
return 0;
}  ```
```// Iterative Solution : Time Complexity : O(LogN),  Aux. Space : O(1)

import java.util.*;
import java.io.*;

class GFG
{
static int bSearch(int arr[], int n, int x)
{
int low = 0, high = n - 1;

while(low <= high)
{
int mid = (low + high) / 2;

if(arr[mid] == x)
return mid;

else if(arr[mid] > x)
high = mid - 1;

else
low = mid + 1;
}

return -1;
}

public static void main(String args[])
{
int arr[] = {10, 20, 30, 40, 50, 60}, n = 6;

int x = 25;

System.out.println(bSearch(arr, n, x));  // Output : -1

}

}

// Recursive Solution : Time Complexity : O(LogN),  Aux. Space : O(logN)

import java.util.*;
import java.io.*;

class GFG
{
static int bSearch(int arr[], int low, int high, int x)
{
if(low > high)
return -1;

int mid = (low + high) / 2;

if(arr[mid] == x)
return mid;

else if(arr[mid] > x)
return bSearch(arr, low, mid - 1, x);

else
return bSearch(arr, mid + 1, high, x);
}

public static void main(String args[])
{
int arr[] = {10, 20, 30, 40, 50, 60, 70}, n = 7;

int x = 20;

System.out.println(bSearch(arr, 0, n - 1, x));  // Output : 1
}
}```
```int firstOccurance(vector<int> &ar,int target){
int low = 0,high = ar.size()-1,ans = -1;
while(low<=high){
int mid = low+(high-low)/2;

if(ar[mid]==target){
//mid can be our answer but we are not sure so reduce the search space
ans = mid;
high = mid-1;//for first occurance go to left
}
else if(ar[mid]>target)
high = mid-1;
else
low = mid+1;
}
return ans;//if element is not present ans will remain -1,and will be returned as it is.
}

int lastOccurance(vector<int> &ar,int target){

int low = 0,high = ar.size()-1,ans = -1;
while(low<=high){
int mid = low+(high-low)/2;

if(ar[mid]==target){
//mid can be our answer but we are not sure so reduce the search space
ans = mid;
low = mid+1; //for lasat occurance go to right
}
else if(ar[mid]>target)
high = mid-1;
else
low = mid+1;
}

return ans;//if element is not present ans will remain -1,and will be returned as it is.
}```
```//whenever there is sorted array first think of binary search

int binarySearch(vector<int> &ar, int target)
{

int low = 0, high = ar.size() - 1;

while (low <= high)
{
int mid = low + (high - low) / 2;

if (ar[mid] == target)
return mid;
else if (ar[mid] > target)
high = mid - 1; // go to left
else
low = mid + 1; // go to right
}

}

//the above solution is only ,if array is sorted in ascending order
//for descending sorted array condition's to go to left and right reverse

//time complexity :- O(logn);
```
star

Thu May 26 2022 15:44:58 GMT+0000 (UTC)

#c #binarysearch
star

Sun Jan 16 2022 07:18:37 GMT+0000 (UTC)

#binarysearch
star

Sun Jan 16 2022 06:59:21 GMT+0000 (UTC)

#binarysearch