Data Structures & Algorithms – Search algorithms (e.g. binary search, linear search)
Search algorithms are a set of methods and techniques used to find a specific item or a set of items in a collection. There are many different search algorithms, each one suited to different types of data and use cases.
Two of the most well-known and widely used search algorithms are binary search and linear search.
Binary search is an efficient algorithm for finding an item in a sorted array. It works by repeatedly dividing the search interval in half. The basic idea is to compare the middle element of the array with the target element, if they are not equal, half of the array is eliminated and the search continues on the remaining half, until the target element is found or the search interval is empty. The time complexity of binary search is O(log n) in the average and worst case.
Here is an example of binary search implemented in Python:
def binary_search(arr, x):
low = 0
high = len(arr) - 1
mid = 0
while low <= high:
mid = (high + low) // 2
if arr[mid] < x:
low = mid + 1
elif arr[mid] > x:
high = mid - 1
else:
return mid
return -1
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
x = 6
result = binary_search(arr, x)
if result != -1:
print(f"Element is present at index {str(result)}")
else:
print("Element is not present in array")
Linear search is a simple search algorithm that checks each element of an array one by one, until the target element is found. The time complexity of linear search is O(n) in the average and worst case.
Here is an example of linear search implemented in Python:
def linear_search(arr, x):
for i in range(len(arr)):
if arr[i] == x:
return i
return -1
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
x = 6
result = linear_search(arr, x)
if result != -1:
print(f"Element is present at index {str(result)}")
else:
print("Element is not present in array")
Here is an example of binary search implemented in JavaScript:
function binary_search(arr, x) {
let low = 0;
let high = arr.length - 1;
let mid = 0;
while (low <= high) {
mid = Math.floor((high + low) / 2);
if (arr[mid] < x) {
low = mid + 1;
} else if (arr[mid] > x) {
high = mid - 1;
} else {
return mid;
}
}
return -1;
}
let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let x = 6;
let result = binary_search(arr, x);
if (result != -1) {
console.log("Element is present at index " + result);
} else {
console.log("Element is not present</code>in array");
}
Here is an example of linear search implemented in JavaScript:
function linear_search(arr, x) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] == x) {
return i;
}
}
return -1;
}
let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let x = 6;
let result = linear_search(arr, x);
if (result != -1) {
console.log("Element is present at index " + result);
} else {
console.log("Element is not present in array");
}
Here is an example of binary search implemented in Java:
public class BinarySearch {
public static int binarySearch(int[] arr, int x) {
int low = 0;
int high = arr.length - 1;
int mid = 0;
while (low <= high) {
mid = (high + low) / 2;
if (arr[mid] < x) {
low = mid + 1;
} else if (arr[mid] > x) {
high = mid - 1;
} else {
return mid;
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int x = 6;
int result = binarySearch(arr, x);
if (result != -1) {
System.out.println("Element is present at index " + result);
} else {
System.out.println("Element is not present in array");
}
}
}
Here is an example of linear search implemented in Java:
public class LinearSearch {
public static int linearSearch(int[] arr, int x) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == x) {
return i;
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int x = 6;
int result = linearSearch(arr, x);
if (result != -1) {
System.out.println("Element is present at index " + result);
} else {
System.out.println("Element is not present in array");
}
}
}
Here is an example of binary search implemented in Rust:
fn binary_search(arr: &[i32], x: i32) -> i32 {
let mut low = 0;
let mut high = arr.len() - 1;
let mut mid = 0;
while low <= high {
mid = (high + low) / 2;
if arr[mid] < x {
low = mid + 1;
} else if arr[mid] > x {
high = mid - 1;
} else {
return mid as i32;
}
}
return -1;
}
fn main() {
let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let x = 6;
let result = binary_search(&arr, x);
if result != -1 {
println!("Element is present at index {}", result);
} else {
println!("Element is not present in array");
}
}
Here is an example of linear search implemented in Rust:
fn linear_search(arr: &[i32], x: i32) -> i32 {
for i in 0..arr.len() {
if arr[i] == x {
return i as i32;
}
}
return -1;
}
fn main() {
let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let x = 6;
let result = linear_search(&arr, x);
if result != -1 {
println!("Element is present at index {}", result);
} else {
println!("Element is not present in array");
}
}
As you can see, both binary search and linear search are implemented similarly in all four languages, with the main difference being the syntax. Linear search is simple and straightforward, but it has a time complexity of O(n), making it less efficient than binary search for large collections. It is important to note that binary search can only be applied on a sorted array, whereas linear search can be applied on any array.