Binary Search Function

Binary Search Function

Medium Programming Interview Algorithms 14 views
Explanation Complexity

Problem Statement

Consider {x}. Output result.

Input Format

First line n. Second line n integers sorted. Third line x.

Output Format

One integer index.

Example

5
1 3 5 7 9
7
3

Constraints

1

Input / Output Format

Input Format
First line n. Second line n integers sorted. Third line x.
Output Format
One integer index.
Constraints
1

Examples

Input:
5 1 3 5 7 9 7
Output:
3

Example Solution (Public)

Programming Interview 
import sys
lines=sys.stdin.read().splitlines()
if len(lines)<3: sys.exit(0)
n=int(lines[0].strip())
a=list(map(int,lines[1].split()[:n]))
x=int(lines[2].strip())
def bsearch(arr,target):
  l=0
  r=len(arr)-1
  while l<=r:
    m=(l+r)//2
    if arr[m]==target:
      return m
    if arr[m]<target:
      l=m+1
    else:
      r=m-1
  return -1
sys.stdout.write(str(bsearch(a,x)))

Official Solution Code

import sys
lines=sys.stdin.read().splitlines()
if len(lines)<3: sys.exit(0)
n=int(lines[0].strip())
a=list(map(int,lines[1].split()[:n]))
x=int(lines[2].strip())
def bsearch(arr,target):
  l=0
  r=len(arr)-1
  while l<=r:
    m=(l+r)//2
    if arr[m]==target:
      return m
    if arr[m]<target:
      l=m+1
    else:
      r=m-1
  return -1
sys.stdout.write(str(bsearch(a,x)))
Please login to submit solutions.
Editor
Output

                                        

                                    

                                    

                                        

                                                                                    
Please login to submit solutions.