[go: up one dir, main page]
Scribd
Upload
8 views3 pages

Unit - 5.1

The document describes two algorithms: binary search and mergesort. Binary search efficiently finds the index of a target value in a sorted array by repeatedly dividing the search interval in half. Mergesort is a divide-and-conquer algorithm that recursively sorts an array by splitting it into halves, sorting each half, and then merging the sorted halves back together.

Uploaded by

vedsin0001
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views3 pages

Unit - 5.1

The document describes two algorithms: binary search and mergesort. Binary search efficiently finds the index of a target value in a sorted array by repeatedly dividing the search interval in half. Mergesort is a divide-and-conquer algorithm that recursively sorts an array by splitting it into halves, sorting each half, and then merging the sorted halves back together.

Uploaded by

vedsin0001
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

function binarySearch(arr, target, n):

low = 0
high = n - 1

while low <= high:


mid = (low + high) / 2 // Integer division

if arr[mid] == target:
return mid // Target found, return index
else if arr[mid] < target:
low = mid + 1 // Search in right half
else:
high = mid - 1 // Search in left half

return -1 // Target not found


Mergesort:-
if left < right then
mid ← (left + right) / 2
MergeSort(arr, left, mid)
MergeSort(arr, mid + 1, right)
Merge(arr, left, mid, right)
end if
n1 ← mid - left + 1
n2 ← right - mid

Create arrays L[1..n1] and R[1..n2]

for i ← 0 to n1 - 1 do
L[i] ← arr[left + i]

for j ← 0 to n2 - 1 do
R[j] ← arr[mid + 1 + j]
i ← 0, j ← 0, k ← left

while i < n1 and j < n2 do


if L[i] ≤ R[j] then
arr[k] ← L[i]
i←i+1
else
arr[k] ← R[j]
j←j+1
k←k+1

while i < n1 do
arr[k] ← L[i]
i←i+1
k←k+1
arr[k] ← R[j]
j←j+1
k←k+1

You might also like