[数据结构与算法]算法总结（java & python）

1、二分查找

概念：假设列表中的数据是升序排列，给定一个目标值，如果在列表中查到与目标值相等的数，则返回该值在列表中的位置，如果没找到则返回-1。

思路：1、先取中间位置的数与目标值相比较，如果相等则返回对应位置的索引；

? ? ? ? ? ? 2、如果目标值小于中间值，则继续比对中间位置左侧的列表，重复步骤1；

? ? ? ? ? ? 3、如果目标值大于中间值，则继续比对中间位置右侧的列表，重复步骤1；

? ? ? ? ? ? 4、最终没有匹配到，返回-1。

java：

    public int search(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        while(start <= end) {
            int middle = (start + end) >>> 1;
            if (target == nums[middle]) {
                return middle;
            }else if(target < nums[middle]) {
                end = middle - 1;
            }else {
                start = middle + 1;
            }
        }
        return -1;
    }

python：

    def search(self, nums, target) :
        start = 0
        end = len(nums) - 1
        while start <= end:
            middle = (start + end) // 2
            if target == nums[middle]:
                return middle
            elif target < nums[middle]:
                end = middle - 1
            else:
                start = middle + 1
        
        return -1