#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Linear Search — O(n)
int linearSearch(const vector<int>& arr, int target) {
for (int i = 0; i < arr.size(); i++)
if (arr[i] == target) return i;
return -1;
}
// Binary Search — O(log n), array must be sorted
int binarySearch(const vector<int>& arr, int target) {
int lo = 0, hi = arr.size() - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // avoid overflow
if (arr[mid] == target) return mid;
if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
// Binary Search — find first occurrence (for duplicates)
int firstOccurrence(const vector<int>& arr, int target) {
int lo = 0, hi = arr.size()-1, result = -1;
while (lo <= hi) {
int mid = lo + (hi-lo)/2;
if (arr[mid] == target) { result = mid; hi = mid-1; } // keep searching left
else if (arr[mid] < target) lo = mid+1;
else hi = mid-1;
}
return result;
}
int main() {
vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};
cout << "Linear search 7: " << linearSearch(arr, 7) << endl; // 3
cout << "Binary search 7: " << binarySearch(arr, 7) << endl; // 3
cout << "Binary search 6: " << binarySearch(arr, 6) << endl; // -1
// STL binary search
cout << boolalpha;
cout << binary_search(arr.begin(), arr.end(), 7) << endl; // true
auto it = lower_bound(arr.begin(), arr.end(), 7); // first >= 7
cout << "lower_bound(7): index " << (it - arr.begin()) << endl; // 3
return 0;
}
import java.util.Arrays;
public class SearchingAlgorithms {
static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++)
if (arr[i] == target) return i;
return -1;
}
static int binarySearch(int[] arr, int target) {
int lo = 0, hi = arr.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
// Search in rotated sorted array
static int searchRotated(int[] arr, int target) {
int lo = 0, hi = arr.length - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (arr[mid] == target) return mid;
if (arr[lo] <= arr[mid]) { // left half is sorted
if (arr[lo] <= target && target < arr[mid]) hi = mid - 1;
else lo = mid + 1;
} else { // right half is sorted
if (arr[mid] < target && target <= arr[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 11, 13, 15};
System.out.println("Linear: " + linearSearch(arr, 7)); // 3
System.out.println("Binary: " + binarySearch(arr, 7)); // 3
// Built-in binary search
System.out.println("Arrays.binarySearch: " + Arrays.binarySearch(arr, 7)); // 3
// Rotated array search
int[] rotated = {4, 5, 6, 7, 0, 1, 2};
System.out.println("Search in rotated: " + searchRotated(rotated, 0)); // 4
}
}
import bisect
# Linear Search — O(n)
def linear_search(arr, target):
for i, x in enumerate(arr):
if x == target: return i
return -1
# Binary Search — O(log n)
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target: return mid
elif arr[mid] < target: lo = mid + 1
else: hi = mid - 1
return -1
arr = [1, 3, 5, 7, 9, 11, 13, 15]
print("Linear:", linear_search(arr, 7)) # 3
print("Binary:", binary_search(arr, 7)) # 3
# Built-in binary search using bisect
idx = bisect.bisect_left(arr, 7)
print("bisect_left:", idx) # 3
# Check if element exists
if idx < len(arr) and arr[idx] == 7:
print("Found at index", idx)
# Search in rotated sorted array
def search_rotated(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target: return mid
if arr[lo] <= arr[mid]: # left half sorted
if arr[lo] <= target < arr[mid]: hi = mid - 1
else: lo = mid + 1
else: # right half sorted
if arr[mid] < target <= arr[hi]: lo = mid + 1
else: hi = mid - 1
return -1
rotated = [4, 5, 6, 7, 0, 1, 2]
print("Rotated search 0:", search_rotated(rotated, 0)) # 4
// Linear Search — O(n)
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++)
if (arr[i] === target) return i;
return -1;
}
// Binary Search — O(log n)
function binarySearch(arr, target) {
let lo = 0, hi = arr.length - 1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
// Binary Search — find insertion point
function lowerBound(arr, target) {
let lo = 0, hi = arr.length;
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (arr[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}
const arr = [1, 3, 5, 7, 9, 11, 13, 15];
console.log("Linear:", linearSearch(arr, 7)); // 3
console.log("Binary:", binarySearch(arr, 7)); // 3
console.log("Lower bound 6:", lowerBound(arr, 6)); // 3 (index where 6 would go)
// Built-in search
console.log("indexOf:", arr.indexOf(7)); // 3 — O(n) linear
console.log("includes:", arr.includes(7)); // true — O(n) linear
// Search in rotated sorted array
function searchRotated(arr, target) {
let lo = 0, hi = arr.length - 1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (arr[mid] === target) return mid;
if (arr[lo] <= arr[mid]) {
if (arr[lo] <= target && target < arr[mid]) hi = mid - 1;
else lo = mid + 1;
} else {
if (arr[mid] < target && target <= arr[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return -1;
}
console.log("Rotated search 0:", searchRotated([4,5,6,7,0,1,2], 0)); // 4