Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Transition Point

Last Updated on April 14, 2022 by Ria Pathak

Binary Search

Easy

### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

Given a sorted array of `0's` and `1's` of size `N`, find the first occurrence of `1` if present else return `-1`.

See original problem statement here

#### For Example:

``````Input : arr = [0, 0, 0, 1, 1]

Output : 3

Explanation : First occurrence of 1 is present at 3rd index.``````

Can we use Binary Search here ?

Given that the array is sorted, `Binary Search` would be an efficient alternative to quickly search for the first occurrence of `1` in `Logarithmic Time Complexity`.

### SOLVING APPROACH:

1. The idea is to use `Binary Search`.

2. Initialize `mid = start + (end - start) / 2` and `flag =-1`, where `start` is the starting index of the array and `end` is the last index.

3. Check if `1` is present at `mid` index, if Yes save this index in `flag` and search for a smaller index by searching in the left sub array by marking, `end = mid -1`.

4. Else keep on searching in the right half by marking
`start` `=` `mid + 1`.

5. Keep doing it till `start` becomes less than equal to `end`, finally return `flag`.

### ALGORITHM:

``````flag = -1

while (start <= end)
mid = start + (end - start) / 2

if (element at mid index = 1)
flag = mid
end = mid - 1

else
start = mid + 1

return flag``````

### SOLUTIONS:

```
#include <stdio.h>

int firstOccurence(int *arr, int start, int end, int flag){
while(start <= end){
int mid = start + (end - start) / 2;
if(arr[mid] == 1){
flag = mid;
end = mid - 1;
}
else{
start = mid + 1;
}
}
return flag;
}

int main()
{
int t; scanf("%d", &t);
while(t--){
int n; scanf("%d", &n);
int arr[n];
for(int i = 0; i<n; i++)
scanf("%d", &arr[i]);
printf("%d\n", firstOccurence(arr, 0, n-1,-1));
}

return 0;
}
```
```
#include <bits/stdc++.h>
using namespace std;

int firstOccurence(int *arr, int start, int end, int flag = -1){
while(start <= end){
int mid = start + (end - start) / 2;
if(arr[mid] == 1){
flag = mid;
end = mid - 1;
}
else{
start = mid + 1;
}
}
return flag;
}

int main()
{
int t; cin>>t;
while(t--){
int n; cin>>n;
int arr[n];
for(int i = 0; i<n; i++)
cin>>arr[i];
cout<<firstOccurence(arr, 0, n-1)<<"\n";
}

return 0;
}
```
```
import java.util.*;
import java.io.*;

public class Main {
static int firstOccurence(int[] arr, int start, int end, int flag){
while(start <= end){
int mid = start + (end - start) / 2;
if(arr[mid] == 1){
flag = mid;
end = mid - 1;
}
else{
start = mid + 1;
}
}
return flag;
}
public static void main(String args[]) throws IOException {

Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t != 0){
int n = sc.nextInt();
int arr[] = new int[n];
for(int i = 0; i<n; i++)
arr[i] = sc.nextInt();
System.out.println(firstOccurence(arr, 0, n-1, -1));
t--;
}
}
}
```

Space Complexity: O(1)
[forminator_quiz id="1651"]

This article tried to discuss Binary Search. Hope this blog helps you understand the concept. To practice more problems you can check out MYCODE | Competitive Programming.