Question

PLEASE BRIEFLY DISCUSS ABOUT THE DEFINITIONS AND SAMPLE CODES FOR
BINARY SEARCH AND TARGET SEARCH

Answer 1

Binary Search:

Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

We basically ignore half of the elements just after one comparison.

1. Compare x with the middle element.
2. If x matches with middle element, we return the mid index.
3. Else If x is greater than the mid element, then x can only lie in right half subarray after the mid element. So we recur for right half.
4. Else (x is smaller) recur for the left half.

# Python 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

# Test array
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"

-------------------------------------------------------------------------------------------------------------------------

# Python code to implement iterative Binary Search.

# It returns location of x in given array array
# if present, else returns -1

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

# Test array
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"

---------------------------------------------------------------------------------------------------------------------------------------

Target Search :

Given a target position on infinite number line, i.e -infinity to +infinity. Starting form 0 you have to reach the target by moving as described : In ith move you can take i steps forward or backward. Find the minimum number of moves require to reach the target.

# Python 3 program to find minimum moves to reach target if we can move i steps in i-th move.

def reachTarget(target) :

   # Handling negatives by symmetry
   target = abs(target)
  
   # Keep moving while sum is
   # smaller or difference is odd.
   sum = 0
   step = 0
   while (sum < target or (sum - target) % 2 != 0) :
       step = step + 1
       sum = sum + step
  
   return step   
target = 5
print(reachTarget(target))