搜索算法旨在检查元素或从存储元素的任何数据结构中检索元素。根据搜索操作的类型，这些算法一般分为两类：

1. 顺序搜索：在这种情况下，列表或数组按顺序遍历并检查每个元素。例如：线性搜索。
2. 间隔搜索：这些算法是专门为在排序的数据结构中搜索而设计的。这些类型的搜索算法比线性搜索更有效，因为它们重复定位搜索结构的中心并将搜索空间分成两半。例如：二分搜索。

难度级别： 基本

最后更新： 2021 年 6 月 28 日

问题：给定一个包含 n 个元素的数组 arr[]，编写一个函数来搜索 arr[] 中的给定元素 x。

例子 ：  

输入： arr[] = {10, 20, 80, 30, 60, 50,
                     110, 100, 130, 170}
          x = 110;
输出： 6
元素 x 出现在索引 6
输入： arr[] = {10, 20, 80, 30, 60, 50,
                     110, 100, 130, 170}
           x = 175;
输出： -1
元素 x 不存在于 arr[] 中。

一种简单的方法是进行线性搜索，即  

从 arr[] 最左边的元素开始，将 x 与 arr[] 的每个元素一一比较

如果 x 与元素匹配，则返回索引。

如果 x 与任何元素都不匹配，则返回 -1。

<script>
// Javascript code to linearly search x in arr[]. If x
// is present then return its location, otherwise
// return -1
function search(arr, n, x)
{
	let i;
	for (i = 0; i < n; i++)
		if (arr[i] == x)
			return i;
	return -1;
}
// Driver code
	let arr = [ 2, 3, 4, 10, 40 ];
	let x = 10;
	let n = arr.length;
	// Function call
	let result = search(arr, n, x);
	(result == -1)
		? document.write("Element is not present in array")
		: document.write("Element is present at index " + result);
// This code is contributed by Manoj
</script>

上述算法的时间复杂度为 O(n)。 

线性搜索在实际中很少使用，因为其他搜索算法（例如二分搜索算法和哈希表）与线性搜索相比可以显着加快搜索速度。

提高线性搜索最坏情况的复杂性

1. 如果元素最后找到 O(n) 到 O(1)
2. 如果未找到元素 O(n) 到 O(n/2)

下面是实现：

<script>
	
// Javascript program for linear search
function search(arr, search_Element)
{
	let left = 0;
	let length = arr.length;
	let right = length - 1;
	let position = -1;
	// Run loop from 0 to right
	for(left = 0; left <= right;)
	{
		
		// If search_element is found
		// with left variable
		if (arr[left] == search_Element)
		{
			position = left;
			document.write(
				"Element found in Array at " +
				(position + 1) + " Position with " +
					(left + 1) + " Attempt");
			break;
		}
		
		// If search_element is found
		// with right variable
		if (arr[right] == search_Element)
		{
			position = right;
			document.write(
				"Element found in Array at " +
				(position + 1) + " Position with " +
				(length - right) + " Attempt");
			break;
		}
		left++;
		right--;
	}
	// If element not found
	if (position == -1)
		document.write("Not found in Array with " +
					left + " Attempt");
}
	
// Driver code
let arr = [ 1, 2, 3, 4, 5 ];
let search_element = 5;
// Function call
search(arr, search_element);
// This code is contributed by code_hunt
</script>

在第 5 个位置的 Array 中找到了 1 次尝试的元素

在一次比较之后，我们基本上忽略了一半的元素。

1. 将 x 与中间元素进行比较。
2. 如果 x 与中间元素匹配，我们返回中间索引。
3. Else 如果 x 大于中间元素，则 x 只能位于中间元素之后的右半子阵列中。所以我们在右半场重复。
4. 否则（x 较小）在左半部分重复出现。

二分查找的递归实现 

<script>
// JavaScript program to implement recursive Binary Search
// A recursive binary search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
function binarySearch(arr, l, r, x){
	if (r >= l) {
		let mid = l + Math.floor((r - l) / 2);
		// If the element is present at the middle
		// itself
		if (arr[mid] == x)
			return mid;
		// If element is smaller than mid, then
		// it can only be present in left subarray
		if (arr[mid] > x)
			return binarySearch(arr, l, mid - 1, x);
		// Else the element can only be present
		// in right subarray
		return binarySearch(arr, mid + 1, r, x);
	}
	// We reach here when element is not
	// present in array
	return -1;
}
let arr = [ 2, 3, 4, 10, 40 ];
let x = 10;
let n = arr.length
let result = binarySearch(arr, 0, n - 1, x);
(result == -1) ? document.write( "Element is not present in array")
				: document.write("Element is present at index " +result);
</script>

在这里您可以创建一个检查功能，以便于实现。

这是带有检查功能的递归实现，我觉得这是一个更简单的实现：

#include <bits/stdc++.h>
using namespace std;
//define array globally
const int N = 1e6 +4;
int a[N];
int n;//array size
//elememt to be searched in array
int k;
bool check(int dig)
{
	//element at dig position in array
	int ele=a[dig];
	//if k is less than
	//element at dig position
	//then we need to bring our higher ending to dig
	//and then continue further
	if(k<=ele)
	{
		return 1;
	}
	else
	{
	return 0;
	}
}
void binsrch(int lo,int hi)
{
	while(lo<hi)
	{
		int mid=(lo+hi)/2;
		if(check(mid))
		{
			hi=mid;
		}
		else
		{
			lo=mid+1;
		}
	}
	//if a[lo] is k
	if(a[lo]==k)
		cout<<"Element found at index "<<lo;// 0 based indexing
	else
		cout<<"Element doesnt exist in array";//element was not in our array
}
int main()
{
	cin>>n;
for(int i=0; i<n; i++)
{
	cin>>a[i];
}
cin>>k;
//it is being given array is sorted
//if not then we have to sort it
//minimum possible point where our k can be is starting index
//so lo=0
//also k cannot be outside of array so end point
//hi=n
binsrch(0,n);
	return 0;
}

二分查找的迭代实现 

<script>
// Program to implement recursive Binary Search
// A recursive binary search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
function binarySearch(arr, l, r, x)
{
	if (r >= l) {
		mid = l + Math.floor((r - l) / 2);
		// If the element is present at the middle
		// itself
		if (arr[mid] == x)
			return mid;
		// If element is smaller than mid, then
		// it can only be present in left subarray
		if (arr[mid] > x)
			return binarySearch(arr, l, mid - 1, x);
		// Else the element can only be present
		// in right subarray
		return binarySearch(arr, mid + 1, r, x);
	}
	// We reach here when element is not
	// present in array
	return -1;
}
	arr =new Array(2, 3, 4, 10, 40);
	x = 10;
	n = arr.length;
	result = binarySearch(arr, 0, n - 1, x);
	
(result == -1) ? document.write("Element is not present in array")
			: document.write ("Element is present at index " + result);
				
// This code is contributed by simranarora5sos
</script>

时间复杂度： 

二分查找的时间复杂度可以写成 

T(n) = T(n/2) + c 

本文链接:https://it72.com/12690.htm