codes/findind_no.cpp at master · avidit11/codes · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
using namespace std;
int main(){
  int nums[100],n,key;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>nums[i];
  }
  cin>>key;
	   if(nums[0]<nums[n-1]){
	        int l=0,h=n-1,ans=-1;
	        while(l<=h){
	            int mid=l+((h-l)/2);
	            if(nums[mid]==key){
	                ans=mid;
	                break;
	            }
	            else if(nums[mid]<key) l=mid+1;
	            else h=mid-1;
	        }
	        return ans;
	    }
	    else{
	        int ans=0,l=0,h=n-1,temp=-1;
	    while(l<=h){
	        int mid=l+((h-l)/2);
	        if(nums[mid]>mid){
	            if(nums[mid+1]<mid+1){
	                ans=mid;
	                break;
	            }
	            else l=mid+1;
	        }
	        else if(nums[mid]<mid) h=mid-1;
	    }
	    if(key>=nums[0]){
	        l=0,h=ans;
	        while(l<=h){
	            int mid=l+((h-l)/2);
	            if(nums[mid]<key) l=mid+1;
	            else if(nums[mid]>key) h=mid-1;
	            else{
	                temp=mid;
	                break;
	            }
	        }
	        if(nums[temp]==nums[temp-1]){
	            temp=temp-1;
	        }
	    }
	    else{
	        l=ans+1,h=n-1;
	        while(l<=h){
	            int mid=l+((h-l)/2);
	            if(nums[mid]<key) l=mid+1;
	            else if(nums[mid]>key) h=mid-1;
	            else{
	                temp=mid;
	                break;
	            }
	        }
	        if(nums[temp]==nums[temp-1]){
	            temp=temp-1;
	        }
	    }
	    return temp;

}