Searching & Sorting.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Code Binary Search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "1 2 5 6 9\n",
      "5\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "n=int(input())\n",
    "li1=[int(x) for x in input().split()]\n",
    "search=int(input())\n",
    "start=0\n",
    "end=n-1\n",
    "while start<=end:\n",
    "    mid=(start+end)//2\n",
    "    if li1[mid]==search:\n",
    "        print(mid)\n",
    "        break\n",
    "    elif li1[mid]>search:\n",
    "        end=mid-1\n",
    "    else:\n",
    "        start=mid+1\n",
    "else:\n",
    "    print(-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Code Bubble Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "1 8 3 4 6\n",
      "1 3 4 6 8 "
     ]
    }
   ],
   "source": [
    "n=int(input())\n",
    "                \n",
    "arr = [int(x) for x in input().split()]\n",
    "    \n",
    "def bubbleSort(arr):\n",
    "    n = len(arr)\n",
    "    for i in range(n-1):\n",
    "        for j in range(0, n-i-1):\n",
    "            if arr[j] > arr[j+1] :\n",
    "                arr[j], arr[j+1] = arr[j+1], arr[j]\n",
    " \n",
    "bubbleSort(arr)\n",
    "for i in range(len(arr)):\n",
    "    print (arr[i],end=\" \")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Code Insertion Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "1 3 6 9 0\n",
      "0 1 3 6 9 "
     ]
    }
   ],
   "source": [
    "n=int(input())\n",
    "arr=[int(x) for x in input().split()]\n",
    "\n",
    "def insertion(arr):\n",
    "    a=len(arr)\n",
    "    for i in range(1,n):\n",
    "        j=i-1\n",
    "        temp=arr[i]\n",
    "        while (j>=0 and arr[j]>temp):\n",
    "            arr[j+1]=arr[j]\n",
    "            j=j-1\n",
    "        arr[j+1]=temp\n",
    "        \n",
    "insertion(arr)\n",
    "for i in range(n):\n",
    "    print(arr[i],end=\" \")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Code Merge Two Sorted Arrays"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "1 5 6 8 9\n",
      "4\n",
      "1 3 6 9\n",
      "1 1 3 5 6 6 8 9 9 "
     ]
    }
   ],
   "source": [
    "n=int(input())\n",
    "arr1=[int(x) for x in input().split()]\n",
    "m=int(input())\n",
    "arr2=[int(x) for x in input().split()]\n",
    "list1=[]\n",
    "i=0\n",
    "j=0\n",
    "while(i<n and j<m):\n",
    "    if arr1[i]<=arr2[j]:\n",
    "        list1.append(arr1[i])\n",
    "        i=i+1\n",
    "    else:\n",
    "        list1.append(arr2[j])\n",
    "        j=j+1\n",
    "while(i<len(arr1)):\n",
    "    list1.append(arr1[i])\n",
    "    i=i+1\n",
    "while(j<len(arr2)):\n",
    "    list1.append(arr2[j])\n",
    "    j=j+1\n",
    "    \n",
    "for i in range(len(list1)):\n",
    "    print(list1[i],end=\" \")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Push Zeros to end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "1 2 0 0 4\n",
      "1 2 4 0 0 "
     ]
    }
   ],
   "source": [
    "n=int(input())\n",
    "arr=[int(x) for x in input().split()]\n",
    "list1=[]\n",
    "list2=[]\n",
    "for i in range(n):\n",
    "    if arr[i]==0:\n",
    "        list2.append(arr[i])\n",
    "    else:\n",
    "        list1.append(arr[i])\n",
    "\n",
    "a=len(list1)+len(list2)\n",
    "list3=[]\n",
    "for i in range(len(list1)):\n",
    "    list3.append(list1[i])\n",
    "for i in range(len(list2)):\n",
    "    list3.append(list2[i])\n",
    "for i in range(a):\n",
    "    print(list3[i],end=\" \")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Rotate array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "1 4 6 9 7\n",
      "2\n",
      "6 9 7 1 4 "
     ]
    }
   ],
   "source": [
    "def Rotate(arr, d):\n",
    "    n=len(arr)\n",
    "    list1=[]\n",
    "    list2=[]\n",
    "    list3=[]\n",
    "    for i in range(d,n):\n",
    "        list1.append(arr[i])\n",
    "    for i in range(0,d):\n",
    "        list2.append(arr[i])\n",
    "    for i in range(len(list1)):\n",
    "        list3.append(list1[i])\n",
    "    for i in range(len(list2)):\n",
    "        list3.append(list2[i])\n",
    "    for i in range(n):\n",
    "        print(list3[i],end=\" \")\n",
    "\n",
    "\n",
    "n=int(input())\n",
    "arr=list(int(i) for i in input().strip().split(' '))\n",
    "d=int(input())\n",
    "Rotate(arr, d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Second Largest in array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "1 2 55 6 9\n",
      "9\n"
     ]
    }
   ],
   "source": [
    "n=int(input())\n",
    "arr=[int(x) for x in input().split()]\n",
    "\n",
    "def print2largest(arr,arr_size): \n",
    "    first = second = -2147483648\n",
    "    for i in range(arr_size): \n",
    "                # first and second  \n",
    "        if (arr[i] > first): \n",
    "          \n",
    "            second = first \n",
    "            first = arr[i]  \n",
    "        elif (arr[i] > second and arr[i] != first): \n",
    "            second = arr[i] \n",
    "    print(second)\n",
    "\n",
    "  \n",
    "print2largest(arr, n) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Check Array Rotation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "5 6 1 2 3\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "# Given an integer array, which is sorted (in increasing order) and \n",
    "# has been rotated by some number k in clockwise direction. Find and return the k.\n",
    "\n",
    "n=int(input())\n",
    "arr=[int(x) for x in input().split()]\n",
    "\n",
    "for i in range(n):\n",
    "    if arr[i]>arr[i+1]:\n",
    "        c=i\n",
    "        break\n",
    "print(c+1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sort 0 1 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "1 0 2 0 2\n",
      "0 0 1 2 2 "
     ]
    }
   ],
   "source": [
    "n=int(input())                \n",
    "arr = [int(x) for x in input().split()]\n",
    "    \n",
    "def sort012( a, arr_size): \n",
    "    lo = 0\n",
    "    hi = arr_size - 1\n",
    "    mid = 0\n",
    "    while mid <= hi: \n",
    "        if a[mid] == 0: \n",
    "            a[lo], a[mid] = a[mid], a[lo] \n",
    "            lo = lo + 1\n",
    "            mid = mid + 1\n",
    "        elif a[mid] == 1: \n",
    "            mid = mid + 1\n",
    "        else: \n",
    "            a[mid], a[hi] = a[hi], a[mid]  \n",
    "            hi = hi - 1\n",
    "    return a\n",
    "\n",
    "sort012(arr,n)\n",
    "for i in range(n):\n",
    "    print(arr[i],end=\" \")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sum of two arrays (error- not correct answer)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "1 0 2 3 6\n",
      "5\n",
      "1 2 3 6 9\n",
      "0 2 2 6 0 5 "
     ]
    }
   ],
   "source": [
    "# Two random integer arrays are given A1 and A2, in which numbers from 0 to 9 are present at \n",
    "# every index (i.e. single digit integer is present at every index of both given arrays).\n",
    "# You need to find sum of both the input arrays (like we add two integers) and \n",
    "# put the result in another array i.e. output array (output arrays should also contain only single digits at every index).\n",
    "# The size A1 & A2 can be different.\n",
    "# Note : Output array size should be 1 more than the size of bigger array and place 0 at the \n",
    "# 0th index if there is no carry. No need to print the elements of output array.\n",
    "\n",
    "\n",
    "n=int(input())\n",
    "arr1=[int(x) for x in input().split()]\n",
    "m=int(input())\n",
    "arr2=[int(x) for x in input().split()]\n",
    "i=n-1\n",
    "j=m-1\n",
    "list1=[]\n",
    "carry=0\n",
    "while (i>=0 and j>=0):\n",
    "    s = arr1[i]+arr2[j]+carry\n",
    "    sum=s%10\n",
    "    carry=s//10\n",
    "    i=i-1\n",
    "    j=j-1\n",
    "    list1.append(sum)\n",
    "while(i>=0):\n",
    "    s = arr1[i]+carry\n",
    "    sum=s%10\n",
    "    carry=s//10\n",
    "    list1.append(sum)\n",
    "while(j>=0):\n",
    "    s = arr2[j]+carry\n",
    "    sum=s%10\n",
    "    carry=s//10\n",
    "    list1.append(sum)\n",
    "if n>=m:\n",
    "    if len(list1)!=n+1:\n",
    "        list1.append(0)\n",
    "else:\n",
    "    if len(list1)!=m+1:\n",
    "        list1.append(0)\n",
    "\n",
    "for i in range(len(list1)-1,-1,-1):\n",
    "    print(list1[i],end=\" \")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}