Skip to content

Commit f3a6acf

Browse files
nishantmlnishantml
committed
binary search
1 parent 05f0511 commit f3a6acf

File tree

2 files changed

+184
-0
lines changed

2 files changed

+184
-0
lines changed

‎.ipynb_checkpoints/Searching-checkpoint.ipynb

Lines changed: 92 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -38,6 +38,98 @@
3838
"linearSearch([2,3,4,5,6,7,8,9],9)"
3939
]
4040
},
41+
{
42+
"cell_type": "code",
43+
"execution_count": 63,
44+
"metadata": {},
45+
"outputs": [
46+
{
47+
"name": "stdout",
48+
"output_type": "stream",
49+
"text": [
50+
"Binary Search using recursion... \n",
51+
"Returns index of x in arr if present, else -1 \n",
52+
"4\n"
53+
]
54+
}
55+
],
56+
"source": [
57+
"# Binary Search using recursion\n",
58+
"def binarySearchRecursion(arr, l, r, x): \n",
59+
" \"\"\"Binary Search using recursion... \\nReturns index of x in arr if present, else -1 \"\"\"\n",
60+
" # Check base case \n",
61+
" if r >= l: \n",
62+
"# mid = l + (r - l) // 2\n",
63+
" mid = int((l+r)//2)\n",
64+
" \n",
65+
" # If element is present at the middle itself \n",
66+
" if arr[mid] == x: \n",
67+
" return mid \n",
68+
" \n",
69+
" # If element is smaller than mid, then it \n",
70+
" # can only be present in left subarray \n",
71+
" elif arr[mid] > x: \n",
72+
" return binarySearchRecursion(arr, l, mid-1, x) \n",
73+
" \n",
74+
" # Else the element can only be present \n",
75+
" # in right subarray \n",
76+
" else: \n",
77+
" return binarySearchRecursion(arr, mid + 1, r, x) \n",
78+
" \n",
79+
" else: \n",
80+
" # Element is not present in the array \n",
81+
" return -1\n",
82+
" \n",
83+
"\n",
84+
"# Driver Code \n",
85+
"print(binarySearchRecursion.__doc__)\n",
86+
"arr = [ 2, 3, 4, 10, 40 ] \n",
87+
"x = 40\n",
88+
"print(binarySearchRecursion(arr, 0, len(arr)-1, x))"
89+
]
90+
},
91+
{
92+
"cell_type": "code",
93+
"execution_count": 64,
94+
"metadata": {},
95+
"outputs": [
96+
{
97+
"name": "stdout",
98+
"output_type": "stream",
99+
"text": [
100+
"Binary Search... \n",
101+
"Returns index of x in arr if present, else -1 \n"
102+
]
103+
},
104+
{
105+
"data": {
106+
"text/plain": [
107+
"4"
108+
]
109+
},
110+
"execution_count": 64,
111+
"metadata": {},
112+
"output_type": "execute_result"
113+
}
114+
],
115+
"source": [
116+
"def binary_search(A,n,T):\n",
117+
" \"\"\"Binary Search... \\nReturns index of x in arr if present, else -1 \"\"\"\n",
118+
" L = 0\n",
119+
" R = n-1\n",
120+
" while L<= R:\n",
121+
" m = int((L+R)//2)\n",
122+
" if A[m] < T:\n",
123+
" L = m+1\n",
124+
" elif A[m]>T:\n",
125+
" R = m-1\n",
126+
" else:\n",
127+
" return m\n",
128+
" return -1\n",
129+
"print(binary_search.__doc__)\n",
130+
"binary_search([ 2, 3, 4, 10, 40 ],5,40)"
131+
]
132+
},
41133
{
42134
"cell_type": "code",
43135
"execution_count": null,

‎Searching.ipynb

Lines changed: 92 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -38,6 +38,98 @@
3838
"linearSearch([2,3,4,5,6,7,8,9],9)"
3939
]
4040
},
41+
{
42+
"cell_type": "code",
43+
"execution_count": 63,
44+
"metadata": {},
45+
"outputs": [
46+
{
47+
"name": "stdout",
48+
"output_type": "stream",
49+
"text": [
50+
"Binary Search using recursion... \n",
51+
"Returns index of x in arr if present, else -1 \n",
52+
"4\n"
53+
]
54+
}
55+
],
56+
"source": [
57+
"# Binary Search using recursion\n",
58+
"def binarySearchRecursion(arr, l, r, x): \n",
59+
" \"\"\"Binary Search using recursion... \\nReturns index of x in arr if present, else -1 \"\"\"\n",
60+
" # Check base case \n",
61+
" if r >= l: \n",
62+
"# mid = l + (r - l) // 2\n",
63+
" mid = int((l+r)//2)\n",
64+
" \n",
65+
" # If element is present at the middle itself \n",
66+
" if arr[mid] == x: \n",
67+
" return mid \n",
68+
" \n",
69+
" # If element is smaller than mid, then it \n",
70+
" # can only be present in left subarray \n",
71+
" elif arr[mid] > x: \n",
72+
" return binarySearchRecursion(arr, l, mid-1, x) \n",
73+
" \n",
74+
" # Else the element can only be present \n",
75+
" # in right subarray \n",
76+
" else: \n",
77+
" return binarySearchRecursion(arr, mid + 1, r, x) \n",
78+
" \n",
79+
" else: \n",
80+
" # Element is not present in the array \n",
81+
" return -1\n",
82+
" \n",
83+
"\n",
84+
"# Driver Code \n",
85+
"print(binarySearchRecursion.__doc__)\n",
86+
"arr = [ 2, 3, 4, 10, 40 ] \n",
87+
"x = 40\n",
88+
"print(binarySearchRecursion(arr, 0, len(arr)-1, x))"
89+
]
90+
},
91+
{
92+
"cell_type": "code",
93+
"execution_count": 64,
94+
"metadata": {},
95+
"outputs": [
96+
{
97+
"name": "stdout",
98+
"output_type": "stream",
99+
"text": [
100+
"Binary Search... \n",
101+
"Returns index of x in arr if present, else -1 \n"
102+
]
103+
},
104+
{
105+
"data": {
106+
"text/plain": [
107+
"4"
108+
]
109+
},
110+
"execution_count": 64,
111+
"metadata": {},
112+
"output_type": "execute_result"
113+
}
114+
],
115+
"source": [
116+
"def binary_search(A,n,T):\n",
117+
" \"\"\"Binary Search... \\nReturns index of x in arr if present, else -1 \"\"\"\n",
118+
" L = 0\n",
119+
" R = n-1\n",
120+
" while L<= R:\n",
121+
" m = int((L+R)//2)\n",
122+
" if A[m] < T:\n",
123+
" L = m+1\n",
124+
" elif A[m]>T:\n",
125+
" R = m-1\n",
126+
" else:\n",
127+
" return m\n",
128+
" return -1\n",
129+
"print(binary_search.__doc__)\n",
130+
"binary_search([ 2, 3, 4, 10, 40 ],5,40)"
131+
]
132+
},
41133
{
42134
"cell_type": "code",
43135
"execution_count": null,

0 commit comments

Comments
 (0)