如何使用伪代码开发线性搜索和二进制搜索算法。?

How to Develop algorithms for linear search and binary search using Pseudo code.?

搜索 array/list 是在数组中查找给定元素,return 是否找到它,return 如果找到它的位置。线性搜索和二分搜索是两种流行的数组搜索算法。

算法

算法程序是为解决问题而遵循的一系列规则。它通常用于处理、计算和替代连接计算机和数学运算。

好的算法的特点

  1. 有限性:算法应该终止无限数量的步骤,并且每个步骤必须在有限的时间内完成。
  2. 输入:算法必须有零个或多个输入,但必须是有限数量的输入。
  3. 输出:算法必须至少有一个理想的结果。
  4. 有效性:一个算法应该是有效的,意味着每一步都应该作为原则,并且应该在有限的时间内执行。
  5. 明确:算法应该清晰明确。它的每个步骤及其 inputs/outputs 都应该清楚,并且必须只有一个含义。
  6. 有限性:算法必须在有限步数后终止。

线性搜索

线性搜索是一种非常基本和简单的搜索算法。在线性搜索中,我们通过从头开始遍历数组来搜索给定数组中的元素或值,直到找到所需的元素或值。 线性搜索的伪代码

Read size,array[size], search from user
    i=0
While i<size
        IF 
            search==array[i]
            write i
            break;
        Else
            i++
        Endif
Endwhile

二分查找

二分搜索是最流行的搜索算法。它是高效的,也是最常用的解决问题的技术之一。

二进制搜索的伪代码

Procedure binary search
   a← sorted array
   b← size of array
   c← value to be searched

   Set lowerBound = 1
   Set upperBound = b

   while c not found
      if upperBound < lowerBound 
         EXIT: c does not exists.
   
      set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
      
      if a[midPoint] < c
         set lowerBound = midPoint + 1
         
      if a[midPoint] > c
         set upperBound = midPoint - 1 

      if a[midPoint] = c
         EXIT: c found at location midPoint
   end while
   
end procedure

算法:-算法是一个循序渐进的过程,它定义了一组指令,按照一定的顺序执行以获得所需的输出。

  1. 线性搜索就是遍历整个数组并搜索它。
  2. Binary Search分而治之整个数组然后搜索进去但是主要条件是数组需要排序

线性搜索:-

int arr[5] = {5, 3, 2, 6, 10};
int target = 6; // key to find in array
int result = -1;
for (int i = 0 ; i < 5; i++) {
      if (arr[i] == target) {
           result = i;
           break;
      }
}
cout << result << endl; // here is your result;

优化线性搜索:- 我们可以以一种更优化的方式执行线性搜索,但需要更多 space 为上面的例子创建一个大小比给定数组大 1 的数组,让它为 6 // 然后在同一数组中获取用户输入并在该数组的最后一个索引处添加键

int n;
cin >> n;
int arr[n+1];
for (int i = 0 ; i < n; i++){
    cin >> arr[i];
}
int target;
cin >> target;
arr[n] = target; // adding target
int result = -1;
int i = 0;
while(arr[i] != target){
    result = i;
    i++;
}

if (result == n){
    result = -1;
}

在上面的算法中我们不需要添加 if always 在循环中我们只需要在结束时检查它。

二进制搜索:-

// Binary Search 
int left = 0;
int right = arr.length() -1;

while(left <= right){
    int mid = left + ((right - left) / 2);
    if (arr[mid] == target){
        result = mid;
        break;
    } else (arr[mid] > target){
        right = mid - 1;
    } else {
        left = mid + 1;
    }
}

带递归的二进制搜索:-

   int binarySearch(int arr[], int left, int right, int target) {
        if (right >= left) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target)
                 return mid;

            if (arr[mid] > target)
                return binarySearch(arr, left, mid - 1, target);

            return binarySearch(arr, mid + 1, right, target);
        }
        return -1; // didn't found the element
}